查找大阶乘中特定数字的计数

Question

我需要计算一个大数的阶乘中特定数字（0 和 9 之间）的计数

#include <stdio.h>
int main()
{
    unsigned long long int x;
    int n , count = 0;
    scanf("%llu %d", &x , &n);
    int i = x - 1;
    while(i > 1)
    {
        x *= i;
        i--;
    }
    while (x>0)
    {
        if(x%10 == n) count++;
        x /= 10;
    }
    printf("%d",count);
    return 0;
}

这对小数字很有效
输入： 7 0
输出： 2
描述：7！ = 5040 其中有两个零
但是大数需要很长时间
输入： 50 2
输出： overflow and time limit!

有什么想法可以在时间上优化这个程序吗？例如，一种计算位数而不计算阶乘的数学方法

Answer 1

我终于找到了答案，这可能对其他人有帮助。

想法正在使用 big numbers multiplication:

#include<stdio.h>

int main()
{
    int n , p;
    scanf("%d %d" , &n , &p);
    int digits[1000] = {1};
    for(int i = 2 ; i <= n ; i++)
    {
        for(int k = 0 ; k < 1000 ; k++) digits[k] *= i;
        for(int k = 0 ; k < 1000 ; k++) if(digits[k] > 9)
            {
                digits[k+1] += digits[k]/10;
                digits[k] %= 10;
            }
    }
    int a , count = 0;
    for(a = 999 ; !digits[a] ; a--);
    a++;
    for (int j = 0;j<a;j++) if(digits[j] == p) count++;
    printf("%d" , count);
}

查找大阶乘中特定数字的计数

find count of specific digits in a large factorial

c

optimization

count

factorial