Задача "Интересное число"

@Darkan · Регистрация: 12.02.2014

Студворк — интернет-сервис помощи студентам

Здравствуйте!
Итак, задача заключается в следующем:
Для заданного числа N найти наименьшее положительное число k, сумма цифр которого равна N и оно (число k) делится на N.
N<=100

Решить задачу нужно без использования массивов и тому подобное, т.е. с использованием простых типов данных.
Пробовал решать перебором, но скорость работы алгоритма не радует, к тому же при больших значениях N, происходит переполнение (при N=100 ответ содержит 14 цифр, что не "влазит" в longint).

Я так понимаю, должна быть некая формула для "конструирования" результата по цифрам, но вот всё никак не могу что-нибудь придумать... Помогите с идеями))

@кот Бегемот · 12.02.2014, 19:28

Решай задачу во FreePascal, там есть int64, для которого 14 цифр - не предел

@Darkan · 12.02.2014, 19:56 **[ТС]**

Решение "в лоб" с помощью Int64 на Делфи. При N=100 программа "висит" довольно-таки долго, много больше 2-х секунд

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function sum(n:Int64):Integer;
var res:Integer;
begin
  res:=0;
  while (n>0) do begin
    res:=res + (n mod 10);
    n:= n div 10;
  end;
  sum:=res;
end;
 
var n,i:Integer;
    t:Int64;
 
begin
  Assign(Input,'input.txt'); Reset(Input);
  Assign(Output,'output.txt'); Rewrite(Output);
 
    Readln(n);
    t:=n;
 
    while (sum(t)<>n) do t:=t+n;
 
    Writeln(t);
 
  Close(Input);
  Close(Output);
end.

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@Darkan 5 / 5 / 6 Регистрация: 12.02.2014 Сообщений: 37

	Задача "Интересное число" 12.02.2014, 19:23. Показов 1837. Ответов 2 Метки нет (Все метки) Здравствуйте! Итак, задача заключается в следующем: Для заданного числа N найти наименьшее положительное число k, сумма цифр которого равна N и оно (число k) делится на N. N<=100 Решить задачу нужно без использования массивов и тому подобное, т.е. с использованием простых типов данных. Пробовал решать перебором, но скорость работы алгоритма не радует, к тому же при больших значениях N, происходит переполнение (при N=100 ответ содержит 14 цифр, что не "влазит" в longint). Я так понимаю, должна быть некая формула для "конструирования" результата по цифрам, но вот всё никак не могу что-нибудь придумать... Помогите с идеями)) 0

@кот Бегемот Платежеспособный зверь 8966 / 4389 / 1655 Регистрация: 28.10.2009 Сообщений: 11,647
	12.02.2014, 19:28
	Решай задачу во FreePascal, там есть int64, для которого 14 цифр - не предел 0