Choose and divide UVA - 10375——埃式筛法+组合数阶乘运算

忘是亡心i 2022-06-15 05:58 129阅读 0赞

Think:  
1埃式筛法+组合数阶乘运算  
2[唯一分解定理(算术基本定理)][Link 1]

[vjudge题目链接][vjudge]

以下为Accepted代码

/*
    Eratosthenes筛法+组合数阶乘运算
    */
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    
    int tp, primes[10004], a[10004], e[10004];
    
    void add_factorial(int n, int d);///表示把结果乘以(n!)^d,d = 1表示乘，d = -1表示除
    void add_integer(int n, int d);
    
    int main()
    {
        int p, q, r, s, i, j;
        double ans;
        ///Eratosthenes筛法得到10000以内的所有素数
        memset(a, 0, sizeof(a));
        tp = 0, a[1] = 1, a[2] = 0;
        for(i = 2; i <= 10000; i++){
            if(!a[i]){
                primes[tp++] = i;
                for(j = i*2; j <= 10000; j += i){
                    a[j] = 1;
                }
            }
        }
        while(scanf("%d %d %d %d", &p, &q, &r, &s) != EOF){
            memset(e, 0, sizeof(e));
            add_factorial(p, 1);
            add_factorial(q, -1);
            add_factorial(p-q, -1);
            add_factorial(r, -1);
            add_factorial(s, 1);
            add_factorial(r-s, 1);
    
            ans = 1.0;
            for(i = 0; i < tp; i++){
                ans *= pow(primes[i], e[i]);
            }
            printf("%.5lf\n", ans);
        }
        return 0;
    }
    void add_factorial(int n, int d){
        for(int i = 1; i <= n; i++)
            add_integer(i, d);
    }
    void add_integer(int n, int d){
        for(int i = 0; i < tp; i++){
            while(n%primes[i] == 0){
                n /= primes[i];
                e[i] += d;
            }
            if(n == 1) break;
        }
    }

[Link 1]: http://baike.baidu.com/link?url=7rI5OBj1jhco0d71IZFOskMKYSNIQcaHN3qsTBXki0cLIDobCRXDFz5S83TomPmnmgNYG46EJP7pFxBvlPUTTXhJPKff930gzn3NOI7z0RaaKPKgAZhMhYkIX8feSn4XhVHczTI_BK1Sor0B08iCxK
[vjudge]: https://vjudge.net/problem/UVA-10375