[UVA160]Factors and Factorials 题解

前言

这道题目本身毫无技术含量珂言,但是输出格式珂以调一年

题解

这道题让我们求\(N!\)中每个质数的个数。

一种方法是直接模拟,枚举\(N!\)中的每个元素,然后暴力查看每个数含有有多少质数。

但是这里我采用了另一种方法,我们知道每个质数对答案的贡献由\(p,p^2,p^2,\dots,p^n\)决定,例如如果是5的阶乘,质数2在2,4中出现了2次,贡献为2,但是实际上\(4\ mod\ 2^2=0\)也就是说,\(2^2\)对答案也产生了贡献,那么这个算法就暴力枚举次方数,然后除法操作直接计算贡献,简单明了。

质数的话当然是直接打表啦。

这道题的输出有坑,我WA了好多次。

首先每个独立的答案前要printf("%3d! =",n),注意是占3位的格式输出,然后第15个数之后要换行,换行以后要与上一行对齐,所以要输出六个空格,然后接下来数与数之间没有空格,直接以占三位的形式输出

代码

#include <cstdio>

int primes[27] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};

int read(){
int x = 0; int zf = 1; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
} int main(){
int n, ans;
while (n = read()){
printf("%3d! =", n);
for (int i = 0; primes[i] <= n; ++i){
ans = 0;
for (int j = primes[i]; j <= n; j *= primes[i])
ans += n / j;
if (i == 15)
printf("\n ");
printf("%3d", ans);
}
printf("\n");
}
return 0;
}
上一篇:MySql基本数据类型(转)


下一篇:[PHP] 算法-数值的整数次方的PHP实现