碼迷,mamicode.com
首頁 > 其他好文 > 詳細

[UVA160]Factors and Factorials 題解

時間:2019-06-26 23:14:41      閱讀:118      評論:0      收藏:0      [點我收藏+]

標簽:元素   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

(0)
(0)
   
舉報
評論 一句話評論(0
登錄后才能評論!
? 2014 mamicode.com 版權所有 京ICP備13008772號-2
迷上了代碼!
25选5历史开奖结果百度