7792. Обычный мальчик

Петя – обычный мальчик. Каждый раз перед началом каждого учебного года у него появляется желание взяться за ум. И в этом году он не отступил от своей цели сразу после начала учебы. Внимательно слушая учителя и выполняя все домашние задания, он стал лучшим учеником в классе.

Учитель заметил успехи Пети и выдал ему самый сложный вариант контрольной по математике. Почти все задания мальчик решил за урок, но с одной так и не справился.

Дано целое положительное число x. Требуется найти число y ≥ x, у которого не менее 100 делителей. Причем число y должно превышать число x не более чем на 1%, то есть должно выполняться неравенство x ≤ y ≤ 1.01x.

Помогите Пете решить эту сложную задачу.

Известно, число 510510 имеет ровно 128 делителей.

Вход. Первая строка ввода содержит число x (1 ≤ x ≤ 10¹⁶).

Выход. Если подходящего числа не существует, то выведите -1, иначе выведите любое подходящие число.

Пример входа	Пример выхода
510000	510510

РЕШЕНИЕ

математика

Анализ алгоритма

Попробуем найти некоторое наименьшее по возможности число k, которое содержит 100 делителей. Пусть оно имеет вид 2^a3^b5^c7^d. Тогда количество его делителей (a + 1) * (b + 1) * (c + 1) * (d + 1) должно превышать 100. Выберем например a = 5, b = 2, c = 2, d = 1 (6 * 3 * 3 * 2 = 108 > 100). Тогда k = 2⁵3²5²7¹ = 32 * 9 * 25 * 7 = 50400.

Пусть x ≥ 100k = 5 040 000. Рассмотрим число (x / 50 400 + 1) * 50 400 ≤ x + 50 400 = 100k + k = 101k. То есть число (x / 50 400 + 1) * 50 400 делится на 50400 и поэтому имеет больше 100 делителей, и при этом не больше 101k (то есть не превосходит x на 1%). Следовательно при x ≥ 5 040 000 в качестве ответа можно вывести число (x / 50 400 + 1) * 50 400.

В противном случае совершим полный перебор. Для заданного x переберем все числа i от x до 1.01x, для каждого такого i вычислим количество делителей. Если для некоторого i это количество не менее 100, то выводим в качестве ответа число i. Иначе подходящего числа не существует.

Реализация алгоритма

Функция Div100 вычисляет количество делителей числа n. Если оно больше или равно 100, возвращаем 1. Иначе возвращаем 0.

int Div100(int n)

{

int c, i, res = 1;

for(i = 2; i <= (int)sqrt(1.0*n); i++)

{

if (n % i == 0)

{

c = 0;

while(n % i == 0)

{

n /= i; c++;

}

res *= (c + 1);

}

}

if (n > 1) res *= 2;

return res >= 100;

}

Основная часть программы. Читаем входные данные.

scanf("%lld",&x);

Если x ≥ 5 040 000, то выводим (x / 50 400 + 1) * 50 400.

if (x >= 5040000)

{

printf("%lld\n",(x / 50400 + 1) * 50400);

return 0;

}

Перебираем i от x до 101 * x / 100. Если количество делителей у числа i не меньше 100, то выводим его.

for(i = x; 100 * i <= 101 * x; i++)

if (Div100(i))

{

printf("%d\n",i);

return 0;

}

Если требуемое число не найдено, то выводим -1.

printf("-1\n");