Question

С++ СИРИУС Факториал Для заданного натурального N найти последнюю ненулевую цифру числа N!. Входные данные Задано число число N(0 ≤ N ≤ 1 000 000). Выходные данные Выведите одно число — последнюю ненулевую цифру факториала числа N. Примеры Ввод 5 Вывод 2 Ввод 8 Вывод 2

Answer 1

#include <bits/stdc++.h>

using namespace std;

int n;

unsigned long long k = 1;

int main() {

   

   ios_base::sync_with_stdio(0);

   cin.tie(0);

   cout.tie(0);

   

   cin >> n;

   while (n > 1) {

       k *= n;

       while (k % 10 == 0)

           k /= 10;

       k %= 10;

       n--;

   }

   cout << k;

}

Для миллиона работает за 0.2 секунды. Сложность, вроде как, получается O(n).

Answer 2

Для решения этой задачи вам потребуется найти количество пятерок и количество двоек в разложении факториала числа N на простые множители.

Поскольку каждая пара двоек и пятерок дает ноль на конце числа, вам необходимо найти минимум из количества двоек и пятерок. Это количество будет определять количество нулей на конце факториала числа N.

Затем вычислите факториал числа N и сохраните его в переменной factorial.

После этого уменьшайте factorial на 10, пока он делится на 10 без остатка. Каждое деление на 10 удаляет ноль справа.

После этого возьмите остаток от деления factorial на 10 и сохраните его в переменной lastDigit.

В конце выведите значение переменной lastDigit, которое будет последней ненулевой цифрой факториала числа N.

Вот пример реализации на C++:

cppCopy code
#include <iostream>

int main() {
    int N;
    std::cin >> N;

    int zeros = 0;
    int fives = 0;
    int twos = 0;

    // Подсчет количества двоек и пятерок
    for (int i = 2; i <= N; i++) {
        int num = i;
        while (num % 2 == 0) {
            num /= 2;
            twos++;
        }
        while (num % 5 == 0) {
            num /= 5;
            fives++;
        }
    }

    zeros = std::min(twos, fives); // Количество нулей на конце факториала

    int factorial = 1;
    for (int i = 2; i <= N; i++) {
        factorial *= i;
        while (zeros > 0 && factorial % 10 == 0) {
            factorial /= 10;
            zeros--;
        }
        factorial %= 1000000; // Чтобы не переполнить переменную
    }

    int lastDigit = factorial % 10; // Последняя ненулевая цифра

    std::cout << lastDigit << std::endl;

    return 0;
}

Это решение использует оптимизацию, чтобы избежать переполнения переменной factorial при вычислении факториала больших чисел. Если вам нужна более точная оценка последней ненулевой цифры для больших чисел, вам может потребоваться использовать другой подход, например, работу с большими числами или применение формулы Стирлинга.