BZOJ 2301 莫比乌斯反演入门

2301: [HAOI2011]Problem b

Description

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

 

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

Output

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

Sample Input

2
2 5 1 5 1
1 5 1 5 2

 

Sample Output

14
3
此题作为我的莫比乌斯反演的入门题

推荐文章 

　　　　https://wenku.baidu.com/view/fbec9c63ba1aa8114431d9ac.html      学习莫比乌斯反演

　　　　https://wenku.baidu.com/view/fbe263d384254b35eefd34eb.html
　　　    http://blog.csdn.net/outer_form/article/details/50590197

简单的说下莫比乌斯反演的作用

　　对于一个函数f(n) 我们很难直接求出它的值,但是我可以求出倍数和或者约束和F(n),那么我们就可以将F通过莫比乌斯反演来得到f,基于容斥思想

　　莫比乌斯反演常用于处理一些gcd的问题

代码如下:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long long LL;

const int maxn = 5e4+;

int p[maxn],mo[maxn],phi[maxn],cnt,sum[maxn];

int a,b,c,d,k;

bool vis[maxn];

void init()

{

    mo[]=;

    phi[]=;

    for(int i=;i<=maxn-;i++){

        if(!vis[i]){

            mo[i]=-;

            phi[i]=i-;

            p[cnt++]=i;

        }

        for(int j=;j<cnt&&(ll)i*p[j]<=maxn-;j++){

            vis[i*p[j]]=true;

            if(i%p[j]==){

                mo[i*p[j]]=;

                phi[i*p[j]]=phi[i]*p[j];

                break;

            }

            mo[i*p[j]]=-mo[i];

            phi[i*p[j]]=phi[i]*(p[j]-);

        }

    }

}

ll solve (int n,int m)

{

    ll ret =  ;

    if (n>m) swap(n,m);

    for (int i=,la=;i<=n;i=la+){

        la = min(n/(n/i),m/(m/i));

        ret+=(long long)(sum[la]-sum[i-])*(n/i)*(m/i);

    }

    return ret;

}

int main()

{

    //freopen("de.txt","r",stdin);

    init();

    int T;

    for (int i=;i<=;++i) sum[i] = sum[i-] + mo[i];

    scanf("%d",&T);

    while (T--){

        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);

        ll ans = solve(b/k,d/k)-solve((a-)/k,d/k)-solve((c-)/k,b/k)+solve((a-)/k,(c-)/k);

        printf("%lld\n",ans);

    }

    return ;

}