HDU 1695 GCD（莫比乌斯反演）

forever97 posted @ 2016年9月13日 08:16 in 数学-莫比乌斯反演 with tags 莫比乌斯反演 , 750 阅读

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=1695

【题目大意】

求出区间[1,b][1,d]中公约数为k的对数，重复的对数只计算一次。

【题解】

我们将b和d调整成b<=d，题目转化为[1,b/k][1,d/k]中互质的数对数，由于重复的对数只计算一次，因此需要再计算一次[1,b/k][1,b/k]，用原先答案减去计算出的一半就是答案。

【代码】

#include <cstdio>
#include <algorithm>
const int N=1000010;
using namespace std;
typedef long long ll;
int T,a,b,c,d,k;
int tot,p[N],miu[N],sum[N],v[N];
void mobius(int n){
    int i,j;
    for(miu[1]=1,i=2;i<=n;i++){
        if(!v[i])p[tot++]=i,miu[i]=-1;
        for(j=0;j<tot&&i*p[j]<=n;j++){
            v[i*p[j]]=1;
            if(i%p[j])miu[i*p[j]]=-miu[i];else break;
        }
    }for(i=1;i<n;i++)sum[i]=sum[i-1]+miu[i];
}
ll cal(int n,int m){
    ll t=0;
    if(n>m)swap(n,m);
    for(int i=1,j=0;i<=n;i=j+1)j=min(n/(n/i),m/(m/i)),t+=(ll)(sum[j]-sum[i-1])*(n/i)*(m/i);
    return t;
}
int Cas;
int main(){
    mobius(1000000);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(b>d)swap(b,d); 
        if(k==0)printf("Case %d: 0\n",++Cas);
        else printf("Case %d: %lld\n",++Cas,cal(b/k,d/k)-cal(b/k,b/k)/2);
    }return 0;
}