2409: 【例】【普及-】【P1591】阶乘数码

内存限制：512 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：9 解决：5

题目描述

求 lns="http://www.w3.org/1998/Math/MathML">�! 中某个数码出现的次数。

输入

第一行为 lns="http://www.w3.org/1998/Math/MathML">�(�≤10)，表示数据组数。接下来 lns="http://www.w3.org/1998/Math/MathML">� 行，每行一个正整数 lns="http://www.w3.org/1998/Math/MathML">�(�≤1000) 和数码 lns="http://www.w3.org/1998/Math/MathML">�。

输出

对于每组数据，输出一个整数，表示 lns="http://www.w3.org/1998/Math/MathML">�! 中 lns="http://www.w3.org/1998/Math/MathML">� 出现的次数。

样例输入 复制 

2
5 2
7 0

样例输出 复制 

1
2

提示

#include<bits/stdc++.h>

using namespace std;
int a[5000];
int main() {
    int t;
    cin >> t;
    while (t--) {
        for (int i = 1; i <= 1001; i++)
            a[i] = 0; //将数组清零。
        a[1] = 1; //必须设为1。不能为0，不然怎么乘都是0。
        int n, i, j, k, m;
        int p = 1, jw = 0; //p代表位数，jw代表进位。
        scanf("%d%d", & n, & m);
        for (i = 2; i <= n; i++) //从2开始，反正任何数乘1还等于它本身。
        {
            jw = 0;
            for (j = 1; j <= p; j++) //高精度*单精度。
            {
                a[j] = a[j] * i + jw; //高精度*单精度+进位。
                jw = a[j] / 10; //设置进位。
                a[j] = a[j] % 10;
            }
            while (jw > 0) //如果还有进位，处理进位。
            {
                a[j] = jw % 10;
                jw /= 10;
                j++;
            }
            p = j - 1;
        }
        int ans = 0;
        for (i = p; i >= 1; i--) //搜索n!里有几个指定数字。
        {
            if (a[i] == m)
                ans++;
        }
        cout << ans << endl; //输出。
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
#define maxn 5000
struct Bigint {
    int len, a[maxn];
    Bigint(int x = 0) {
        memset(a, 0, sizeof(a));
        for (len = 1; x; len++)
            a[len] = x % 10, x /= 10;
        --len;
    }
    int & operator[](int i) {
        return a[i];
    }
    void flatten(int L) {
        len = L;
        for (int i = 1; i <= L; ++i) {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        for (; !a[len];)
            len--;
    }
    void print() {
        for (int i = max(len, 1); i >= 1; --i)
            printf("%d", a[i]);
    }
};
Bigint operator + (Bigint & a, Bigint & b) {
    Bigint c;
    int len = max(a.len, b.len);
    for (int i = 1; i <= len; ++i)
        c[i] += a[i] + b[i];
    c.flatten(len + 1);
    return c;
}
Bigint operator * (Bigint & a, int b) {
    Bigint c;
    int len = a.len;
    for (int i = 1; i <= len; ++i)
        c[i] = a[i] * b;
    c.flatten(len + 11);
    return c;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        Bigint fac(1);
        int i, n, m;
        cin >> n >> m;
        for (i = 1; i <= n; ++i) {
            fac = fac * i;
        }
        int ans = 0;
        for (i = fac.len; i >= 1; i--) //搜索n!里有几个指定数字。
        {
            if (fac[i] == m)
                ans++;
        }
        cout << ans << endl; //输出。      
    }
    return 0;
}


来源/分类

提交提交记录统计露一手!