[hdu1695] GCD [莫比乌斯反演]

题面：

传送门

思路：

100000*100000，n方算法T掉，所以必须考虑更好的简化运算的数学方法

注意到要求gcd(x,y)==e，而gcd(x,y)*m=gcd(x*m,y*m)

我们把b和d都除以e，用新的b和d范围来求gcd(x,y)==1，答案再乘上去就好了

具体方法考虑使用莫比乌斯反演：

设函数$F(d)=sum_{i=1}^{n/e}sum_{j=1}^{m/e} [d|gcd(x,y)]$

函数$f(d)=sum_{i=1}^{n/e}sum_{j=1}^{m/e} [gcd(x,y)==d]$

显然$F(d)=sum_{d|i}f(i)$

此时F(x)与f(x)满足莫比乌斯反演的第二种情况

又由前文定义得，我们要求的实际上就是f(1)（在新的b和d下），加上一点去重

$f(1)=sum_{d=1}^{min(b/e,d/e)}mu(d)F(d)$

Code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define ll long long
 6 using namespace std;
 7 bool vis[100010];int mu[100010],pri[100010],cnt=0;
 8 void init(){
 9     int i=1,j,k;
10     mu[i]=1;
11     for(i=2;i<=100000;i++){
12         if(!vis[i]) pri[++cnt]=i,mu[i]=-1;
13         for(j=1;j<=cnt;j++){
14             k=i*pri[j];if(k>100000) break;
15             vis[k]=1;
16             if(i%pri[j]==0){mu[k]=0;break;}
17             else mu[k]-=mu[i];
18         }
19     }
20 }
21 inline int read(){
22     int re=0,flag=1;char ch=getchar();
23     while(ch>'9'||ch<'0'){
24         if(ch=='-') flag=-1;
25         ch=getchar();
26     }
27     while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
28     return re*flag;
29 }
30 int main(){
31     int i,a,b,c,d,e,T=read(),cases=0;ll ans,anss;
32     init();
33     while(T--){
34         a=read();b=read();c=read();d=read();e=read();ans=0;anss=0;
35         if(!e){printf("Case %d: %d
",++cases,0);continue;}
36         b/=e;d/=e;
37         if(b>d) swap(b,d);
38         for(i=1;i<=b;i++) ans+=(ll)mu[i]*(b/i)*(d/i);
39         for(i=1;i<=b;i++) anss+=(ll)mu[i]*(b/i)*(b/i);
40         printf("Case %d: %lld
",++cases,ans-anss/2);
41     }
42 }