[UVA160]Factors and Factorials 題解

標簽：元素   while   getc   main   cto   ==   factorial   ret   etc   

前言

這道題目本身毫無技術含量珂言，但是輸出格式珂以調一年

題解

這道題讓我們求\(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;
}

[UVA160]Factors and Factorials 題解

標簽：元素   while   getc   main   cto   ==   factorial   ret   etc   

原文地址：https://www.cnblogs.com/linzhengmin/p/11094430.html