【埃式筛法】My pretty girl Noora CodeForces - 822D

Myth丶恋晨 2022-06-10 14:22 168阅读 0赞

Think:  
1知识点：埃式筛法+递推  
2题意：n个女生参加选美大赛，每次分成n/x组，每组进行x\*(x-1)/2次比较，然后晋级n/x名女生，不断分组，不断选拔，最终只留下1名女生作为冠军，f\[n\]表示n名女生决出冠军的最少比较次数(通过改变x可影响f\[x\]).  
输入t, l , r (1 ≤ t < 1e9 + 7, 2 ≤ l ≤ r ≤ 5·1e6)  
求解:t^0·f(l) + t^1·f(l + 1) + … + t^(r - l)·f(r)

3借鉴前辈解题思路：  
![这里写图片描述][SouthEast]  
4反思：  
1>方法要立足理解题意，一开始未认真分析就使用快速幂进而超时  
2>t^()未注意及时取模，导致Wrong Answer

[vjudge题目链接][vjudge]

[建议参考博客1][1]  
[建议参考博客2][2]

以下为Time Limit Exceeded代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int mod = 1000000007;
    const int N = 5001400;
    
    int prim[N], tp, link[N];
    LL f[N];
    
    void get_primes();
    void get_f();
    LL find_primes(LL x);
    LL power(LL x, int k, int mod);
    
    int main(){
        get_primes();
        get_f();
        LL x, sum;
        int l, r, k, i;
        while(~scanf("%lld %d %d", &x, &l, &r)){
            sum = 0;
            for(k = 0, i = l; i <= r; i++, k++){
                sum = (sum + power(x, k, mod)*f[i]) % mod;
            }
            printf("%lld\n", sum);
        }
        return 0;
    }
    void get_primes(){
        tp = 0;
        memset(prim, 0, sizeof(prim));
        prim[1] = 1, prim[2] = 0;
        for(LL i = 2; i < N; i++){
            if(!prim[i]){
                link[tp++] = i;
                for(LL j = i*i; j < N; j += i){
                    prim[j] = 1;
                }
            }
        }
    }
    void get_f(){
        for(LL i = 2; i < N; i++){
            if(!prim[i])
                f[i] = i*(i-1)/2;
            else {
                LL t = find_primes(i);
                f[i] = (i/t)*f[t] + f[i/t];
            }
            f[i] %= mod;
        }
    }
    LL find_primes(LL x){
        LL ans;
        for(LL i = 0; i < tp; i++){
            if(x % link[i] == 0){
                ans = link[i];
                break;
            }
        }
        return ans;
    }
    LL power(LL x, int k, int mod){
        LL ans = 1;
        while(k){
            if(k & 1)
                ans = (ans*x) % mod;
            x = (x*x) % mod;
            k >>= 1;
        }
        return ans;
    }

以下为Wrong Answer代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int mod = 1000000007;
    const int N = 5001400;
    
    int prim[N], tp, link[N];
    LL f[N];
    
    void get_primes();
    void get_f();
    LL find_primes(LL x);
    
    int main(){
        get_primes();
        get_f();
        LL x, sum, po;
        int l, r, i;
        while(~scanf("%lld %d %d", &x, &l, &r)){
            sum = 0, po = 1;
            for(i = l; i <= r; i++){
                sum = (sum + po*f[i]) % mod;
                po *= x;
            }
            printf("%lld\n", sum);
        }
        return 0;
    }
    void get_primes(){
        tp = 0;
        memset(prim, 0, sizeof(prim));
        prim[1] = 1, prim[2] = 0;
        for(LL i = 2; i < N; i++){
            if(!prim[i]){
                link[tp++] = i;
                for(LL j = i*i; j < N; j += i){
                    prim[j] = 1;
                }
            }
        }
    }
    void get_f(){
        for(LL i = 2; i < N; i++){
            if(!prim[i])
                f[i] = i*(i-1)/2;
            else {
                LL t = find_primes(i);
                f[i] = (i/t)*f[t] + f[i/t];
            }
            f[i] %= mod;
        }
    }
    LL find_primes(LL x){
        LL ans;
        for(LL i = 0; i < tp; i++){
            if(x % link[i] == 0){
                ans = link[i];
                break;
            }
        }
        return ans;
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int mod = 1000000007;
    const int N = 5001400;
    
    int prim[N], tp, link[N];
    LL f[N];
    
    void get_primes();
    void get_f();
    LL find_primes(LL x);
    
    int main(){
        get_primes();
        get_f();
        LL x, sum, po;
        int l, r, i;
        while(~scanf("%lld %d %d", &x, &l, &r)){
            sum = 0, po = 1;
            for(i = l; i <= r; i++){
                sum = (sum + po*f[i]) % mod;
                po = (po*x) % mod;
            }
            printf("%lld\n", sum);
        }
        return 0;
    }
    void get_primes(){
        tp = 0;
        memset(prim, 0, sizeof(prim));
        prim[1] = 1, prim[2] = 0;
        for(LL i = 2; i < N; i++){
            if(!prim[i]){
                link[tp++] = i;
                for(LL j = i*i; j < N; j += i){
                    prim[j] = 1;
                }
            }
        }
    }
    void get_f(){
        for(LL i = 2; i < N; i++){
            if(!prim[i])
                f[i] = i*(i-1)/2;
            else {
                LL t = find_primes(i);
                f[i] = (i/t)*f[t] + f[i/t];
            }
            f[i] %= mod;
        }
    }
    LL find_primes(LL x){
        LL ans;
        for(LL i = 0; i < tp; i++){
            if(x % link[i] == 0){
                ans = link[i];
                break;
            }
        }
        return ans;
    }

[SouthEast]: /images/20220610/01082f084965491a8b2fe1a51eadba30.png
[vjudge]: https://cn.vjudge.net/contest/180836#problem/D
[1]: http://www.cnblogs.com/fu3638/p/7115096.html
[2]: http://www.cnblogs.com/yyf0309/p/7275184.html?utm_source=itdadao&utm_medium=referral