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

Question

我需要计算特定数字的计数（介于0之间

#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
输出：溢出和时间限制

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




Answer 1

最后我找到了我的答案，这可能对其他人有帮助。

这个想法是使用大数乘法：

#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);
}