【洛谷 P1591】阶乘数码 题解（模拟+高精度）

阶乘数码 题解（模拟+高精度）"/>

【洛谷 P1591】阶乘数码 题解（模拟+高精度）

阶乘数码

题目描述

求 n ! n! n! 中某个数码出现的次数。

输入格式

第一行为 t ( t ≤ 10 ) t(t \leq 10) t(t≤10)，表示数据组数。接下来 t t t 行，每行一个正整数 n ( n ≤ 1000 ) n(n \leq 1000) n(n≤1000) 和数码 a a a。

输出格式

对于每组数据，输出一个整数，表示 n ! n! n! 中 a a a 出现的次数。

样例 #1

样例输入 #1

2
5 2
7 0

样例输出 #1

1
2

思路

先求高精度阶乘，然后统计对应数字出现的次数。

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e7 + 7;int *multiply(int *x, int y, int &l)
{int *r = new int[N];memset(r, 0, sizeof(r));int ln = l;for (int i = 0; i < l; i++){int mul = x[i] * y;int sum = r[i] + mul;r[i] = sum % 10;int c = sum / 10;// 处理进位for (int j = i + 1; c > 0; j++){int sum = r[j] + c;r[j] = sum % 10;c = sum / 10;ln = max(ln, j + 1);}}delete[] x;x = nullptr;l = ln;return r;
}int main()
{int t;cin >> t;while (t--){int n, m;int cnt = 0;cin >> n >> m;int len = 1;int *a = new int[N];a[0] = 1;for (int i = 1; i <= n; i++){a = multiply(a, i, len);}// 求m出现的次数for (int i = len - 1; i >= 0; i--){// cout << a[i];if (a[i] == m){cnt++;}}// cout << endl;cout << cnt << endl;delete[] a;a = nullptr;}
}