Определить, каким количеством цифр "0" заканчивается запись числа N! в K-ичной системе счисления - C (СИ) (148885)

Формулировка задачи:

Факториалом натурального числа N (обозначается N!) Называется произведение всех натуральных чисел от 1 до N включительно: N! = 1 × 2 × 3 × ... × N. Нужно определить, каким количеством цифр "0" заканчивается запись числа N! в K-ичной системе счисления.

// factorial.cpp: определяет точку входа для консольного приложения.
/* Факториалом натурального числа N (обозначается N!) 
Назывется произведение всех натуральных чисел от 1 до N включительно:
N! = 1 Г— 2 Г— 3 Г— ... Г— N.
Нужно определить, каким количеством цифр "0"
заканчивается запись числа N! в K-ичной системе счисления.
 
*/

#include "stdafx.h"
 
#include <windows.h>
#include <iostream> 
#include <string>

using namespace std;
 
string zel(int a[], int la, int q, int p, string u)
{
    string c = "";
    int snos, j;
    do
    {
        j = 0;
        snos = 0;
        for (int i = 0; i<la; i++)
        {
            snos *= q;
            snos += a[i];
            if ((snos<p) && (i) && (j)) { a[j] = 0; j++; }
            if (snos >= p)
            {
                a[j] = snos / p;
                snos = snos%p;
                j++;
            }
        }
        c = u[snos] + c;
        la = j;
    } while (la);
    return c;
}

int fact(int x)
{
    if (x == 1)
        return 1;
    else
        return x*fact(x - 1);
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
    int n=0;
    INT m = 0;
 
    //Вычислляем факториал
    printf("Введите число n: ");
    scanf("%d", &n);
    m = fact(n);
    n <= 0 ? printf("Nevernoe znachenie!\n") : printf("%d! = %d\n", n, m);
 
 //Переводим факториал в конечную систему счисления     
    string u("0123456789ABCDEF"), a;
    int q, p;
    cout << "Введите число: "; cin >> a;
    cout << "Введите исходную систему счисления: "; cin >> q;
    cout << "Введите конечную систему счисления: "; cin >> p;
    int la = a.size();
    int *array = new int[la];
    for (int i = 0; i <= la; i++) array[i] = u.find(toupper(a[i]));
    cout << string(80, '_') << zel(array, la, q, p, u) << endl;

    //считаем число цифр 0
    system("pause");
    return 0;
}

Решение задачи: «Определить, каким количеством цифр "0" заканчивается запись числа N! в K-ичной системе счисления»

Листинг программы

#include <iostream>
using namespace std;
 
int f(int n, int i) { return n ? n/i + f(n/i, i) : 0; }
 
int g(int n, int k) {
    int r=n;
    for (int i=2; i*i<=k; i++) {
        int p=0;
        while (k%i==0) {p++; k/=i;}
        if (p) r = min(r, f(n,i)/p);
    }
    if (k>1) r = min(r, f(n,k));
    return r;
}
 
int main() { int n,k; cin>>n>>k; cout<<g(n, k); }

Объяснение кода листинга программы

В этом коде решается задача о определении количества цифр 0 в записи числа N! в K-ичной системе счисления. Список действий:

В функции f(n, i) происходит вычисление факториала числа n. Рекурсивный алгоритм вычисляет значение n/i и вызывает функцию f(n/i, i) до тех пор, пока n/i не станет равным 0. Когда это произойдет, функция возвращает сумму всех полученных значений.
В функции g(n, k) происходит вычисление количества цифр 0 в записи числа n в K-ичной системе счисления. Функция использует алгоритм поиска простых делителей числа k и находит наименьшее значение p, которое является количеством цифр 0 в записи числа n в K-ичной системе счисления. Если k больше 1, то функция использует функцию f(n, k) для вычисления количества цифр 0 в записи числа n в K-ичной системе счисления.
В функции main() происходит ввод чисел n и k с помощью функции cin, а затем выводится результат вычисления функции g(n, k) с помощью функции cout.