3

Дано целое число 1 < n < 10^9. Надо написать программу на С++, которая ищет количество нулей в числе n! в системе счисления 225. Нужен какой-то хитрый алгоритм, что-бы не искать сам факториал, ибо он огромен.

4
  • 1
    Возможно, количество нулей в конце числа?
    – Chorkov
    20 янв 2017 в 15:24
  • чую попытка посчитать факториал N=10^9-1 очень быстро закончится OutOfMemoryException :)
    – teran
    20 янв 2017 в 15:31
  • @teran Если не ошибаюсь, 9 гигабайт для записи должно хватить :)
    – Harry
    20 янв 2017 в 15:45
  • В более общем виде это было здесь 2 фев 2017 в 8:34

2 ответа 2

6

Вам нужно по сути подсчитать, на какую степень 255 делится число n! Поскольку разложение 225 на простые множители — 5² × 3², вам нужно подсчитать степень 5 и степень 3, на которую делится ваше число.

Согласно википедии, степень k простого числа p, на которую делится n! вычисляется так:

int maxPowerOf(int p, int n)
{
    int k = 0;
    int powerOfP = 1;
    while (true)
    {
        powerOfP *= p;
        int addend = n / powerOfP;
        if (addend == 0)
            return k;
        k += addend;
    }
}

Имея это, вы вычисляете ваши степени:

int p3 = maxPowerOf(3, n);
int p5 = maxPowerOf(5, n);

Степени чисел 9 и 25, на которые делится n!, равны соответственно

int p9 = p3 / 2;
int p25 = p5 / 2;

(поскольку 25 = 5² и 9 = 3²), и искомая степень числа 225, на которую делится n!, есть

min(p9, p25)

Пока я писал ответ, @Harry уже написал то же самое. Оставляю только из-за кода.

1
  • Можно упомянуть, что min(p3, p25) == p25 для n! и p25 = p5 // 2 так как 25==5**2. Похоже работает
    – jfs
    21 янв 2017 в 15:19
5

225 - это 9*25. Тройки входят в факториал куда чаще, так что нужно считать пятерки.

Пересчитайте количество вхождений пятерок. Сначала - кратные 5 - их n/5 (деления целочисленные). Потом - кратные 25 - n/25. Потом - 125... И так далее, и просуммируйте их все. Так как нам нужны 25 - поделите на 2. Это и будет количество нулей. Если, конечно, имеется в виду количество нулей в конце числа :)

"По-моему, так" (с) Пух

По моим расчетам, для 1000000000! количество искомых нулей - 124999999.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.