題目描述
求n!中某個數位出現的次數。輸入格式
第一行為t(≤10),表示資料組數。接下來t行,每行一個正整數n(≤1000)和數位a。輸出格式
對于每組資料,輸出一個整數,表示n!中a出現的次數。輸入輸出樣例
輸入 #1輸出 #12 5 2 7 0
1 2
原題:https://www.luogu.com.cn/problem/P1591
高精階乘,算完後統計下出現了多少個a即可。先放AC代碼:
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
//手動memset整個數組為-1
void bitset(char *s, int n)
{
for (int i = 0; i < n; ++i)
s[i] = -1;
}
//将-1作為數組結束的标志來複制數組
void arrcpy(char *s, char *s2)
{
for (int i = 0; s2[i] != -1; ++i)
s[i] = s2[i];
}
//以-1為數組結束的标志來計算數組内的有效長度
int len(char *s)
{
int res = 0;
while (s[res++] != -1)
;
return res - 1;
}
//輸出數組,用于debug
void show(char *s)
{
for (int i = 0; s[i] != -1; ++i)
cout << char(s[i] + '0');
cout << endl;
}
LL fa(int n, int a)
{
char f1[10000];
char f2[4];
char res[10000];
bitset(f1, 10000);
bitset(f2, 4);
bitset(res, 10000);
f1[0] = 1;//初始為1
int l1;//l1 為 f1的有效長度,l2為f2的有效長度
for (int i = 1; i <= n; ++i)
{
bitset(f2, 4);
int tmp = i;
int l2 = 0;
while (tmp)//構造每次的乘數
{
f2[l2++] = tmp % 10;
tmp /= 10;
}
l1 = len(f1);//由于每輪都會将res拷貝到f1裡,是以需要統計一次長度
int m;
for (int j = 0; j < l1; ++j)
{
m = 0;
int k;
for (k = 0; k < l2; ++k)
{
m += f1[j] * f2[k];
if (res[j + k] > 0)
m += res[j + k];
res[j + k] = m % 10;
m /= 10;
}
if (m)
res[j + k] = (res[j + k] > 0 ? res[j + k] : 0) + m;
}
bitset(f1, 10000);
arrcpy(f1, res);
bitset(res, 10000);
//show(f1);
}
//統計a出現的次數
int c = 0;
for (int i = 0; f1[i] >= 0; ++i)
if (f1[i] == a)
++c;
return c;
}
int main()
{
//freopen("1.txt", "r", stdin);
int t;
cin >> t;
int n, a;
while (t--)
{
cin >> n >> a;
cout << fa(n, a) << endl;
}
return 0;
}
我這裡使用三個char數組來存放兩個乘數和積,每計算完一次就把res數組拷貝到f1數組裡繼續下一輪計算,要注意的是高精乘法必須得有一個數組來放計算結果,一共需要三個數組,加法則可以不用,隻需要兩個數組,另外,由于題目沒要求輸出之類的,是以計算過程中所有數字都是倒序的,也不用翻轉了。