美文网首页
情人节的礼物 HAOI2011 Pro B - 莫比乌斯反演

情人节的礼物 HAOI2011 Pro B - 莫比乌斯反演

作者: 苏子旃 | 来源:发表于2019-02-14 12:04 被阅读0次

    Description
    对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。
    Input Format
    第一行一个整数n,接下来n行每行五个整数,分别表示a,b,c,d,k

    Output Format
    n行,每行一个整数表示满足要求的数对(x,y)的个数

    Sample Input

    2
    2 5 1 5 1
    1 5 1 5 2

    Sample Output

    14
    3

    Constraints
    对于100%的数据,满足1 \leq n \leq 50000,1 \leq a \leq b \leq 50000,1 \leq d \leq c \leq 50000,1 \leq k \leq 50000

    CCYOS
    关键是一个容斥
    ANS(N,M)表示有多少正整数对x,y,满足x<=N,y<=M,并且gcd(x,y)=k。(k题中已给出)
    经过以下推导:

    这是基础
    这是ANS(b,d) - ANS(b,c - 1),记作O
    这是ANS(a - 1,d) - ANS(a - 1,c - 1),记作C
    O - C得到所求 即 ans = ANS(b,d) - ANS(b,c - 1) - (ANS(a - 1,d) - ANS(a - 1,c - 1)) 注意边界条件。
    余下推导同POI2007 ZAP
    code
    #include<bits/stdc++.h>
    using namespace std;
    
    #define mxn 60005
    int T,a,b,c,d,k,cnt;
    int mu[mxn],vis[mxn],prime[mxn],sum[mxn];
    
    inline int read(){
        char c = getchar();
        int fl = 1,ret = 0;
        for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
        for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
        return fl ? ret : -ret;
    }
    
    inline void get_mu(int n){
        mu[1] = 1;
        for(int i = 2;i <= n;++i){
            if(!vis[i])prime[++cnt] = i,mu[i] = -1;
            for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
                vis[i * prime[j]] = 1;
                if(!(i%prime[j]))break;
                else mu[i*prime[j]] = -mu[i];
            }
        }
        for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + mu[i];
    }
    
    inline long long ANS(int N,int M){
        int limit = min(M,N);
        long long ret = 0;
        for(int l = 1,r;l <= limit;l = r + 1){
            r = min(N/(N/l),M/(M/l));
            ret += 1ll * (N/(l*k)) * (M/(l*k)) * (sum[r] - sum[l - 1]);
        }
        return ret;
    }
    
    int main(){
        //freopen("P3455.in","r",stdin);
    //  freopen("P3345.out","w",stdout);
        T = read();
        get_mu(50000);
        for(int t = 1;t <= T;++t){
            a = read();b = read();c = read();d = read();k = read();
            long long ans = 0;
            ans += ANS(b,d) + ANS(a - 1,c - 1);
            ans =ans - ANS(a - 1,d) - ANS(b,c - 1);
            printf("%lld\n",ans);
        }
        return 0;
    }   
    

    相关文章

      网友评论

          本文标题:情人节的礼物 HAOI2011 Pro B - 莫比乌斯反演

          本文链接:https://www.haomeiwen.com/subject/pqteeqtx.html