【題目描述】
HYSBZ - 1101
【題目分析】
昨天測試出了一道差不多的題目，我只能想到暴力，各種優化，最后都是運行了好久TLE，最后才知道要用到莫比烏斯反演，就想著今天研究一下，得出的結論就是，我可能研究不來。。。
//要用到數論的知識，我連人家的基本的定義都理解不了，更不要說證明了。現在只能說學會用吧，我知道這里的莫比烏斯反演可以快速求出[1,n]和[1,m]中所有互質的數字的數目，當作板子用了吧。
這兩天研究了一下數論函數，回來再看這道入門題覺得。。。
學習了一下除法分塊，具體的那個推導我還是沒有理解，但是大概知道怎么用了。
首先因為要求的是gcd(x,y)=d的，我們就要想到轉換成互質來做（很多都是這樣，因為互質有很多性質有很多函數我們可以進行處理），即求所有的gcd(x,y)=1，其中1<=x<=a/d,1<=y<=b/d，關于等于1的等式我們要聯想到元函數，然后進行用莫比烏斯函數和恒等函數卷積展開（就是著名的莫比烏斯反演，其實只是卷積中很簡單的一種。）再根據和式的性質：求的是所有能夠整除gcd(i,j)（1<=i<=a/d,1<=j<=b/d）的數字k的莫比烏斯函數和，我們從k的角度來看，對于每一個k，能夠同時被他整除的個數為(a/d/k) * (b/d/k)，而且k的取值范圍是1<=k<=min(a/d,b/d),所以我們將式子的形式改變一下就得到對k進行求和的式子，然后用除法分塊處理，最后的時間復雜度應該是O(sqrt(n))
自己實現了一下，直接A了。
【AC代碼】
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>#include<algorithm>using namespace std;typedef long long ll;int a,b,k;
int ans;
const int MAXN=50005;
const int MAXM=10005;
int prime[MAXN+5];
int check[MAXN+5];
int mobi[MAXN+5];
int sum[MAXN+5];
int tot=0;void creat_prime()
{mobi[1]=1;for(int i=2;i<MAXN;i++){if(check[i]==0){prime[tot++]=i;mobi[i]=-1; }for(int j=0;j<tot&&prime[j]*i<MAXN;j++){check[prime[j]*i]=1;if(i%prime[j]==0){mobi[prime[j]*i]=0;break;}else{mobi[prime[j]*i]=-mobi[i];}}}for(int i=1;i<=MAXN;i++){sum[i]=sum[i-1]+mobi[i];}
}int solve(int n,int m)
{n/=k; m/=k;if(n>m) swap(n,m); if(n==0) return 0;int next,next1,next2;int tot=0;for(int i=1;i<=n;i=next){next1=n/(n/i); next2=m/(m/i);next=min(next1,next2);tot+=(n/i)*(m/i)*(sum[next]-sum[i-1]);next++;}return tot;
}int main()
{creat_prime();//check[2]=1;int T,u,v,w,flag;scanf("%d",&T);while(T--){ans=0;scanf("%d%d%d",&a,&b,&k);ans=solve(a,b);//這里有可能需要用容斥來計算其他區間的互質的數目，比如如果計算的是[a,b]和[c,d]，那么ans=solve(b,d)-solve(a-1,d)-solve(b,c-1)+solve(a-1,c-1);printf("%d\n",ans);}return 0;
}
自己實現的代碼：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<ctime>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e4+5;int prime[MAXN],mobius[MAXN],sum[MAXN];
bool check[MAXN];
int tot;void pre()
{tot=0; mobius[1]=1; sum[1]=1;for(int i=2;i<MAXN;i++){if(!check[i]){prime[tot++]=i; mobius[i]=-1;}for(int j=0;j<tot && prime[j]*i<MAXN;j++){check[prime[j]*i]=true;if(i%prime[j]) mobius[prime[j]*i]=-mobius[i];else{mobius[prime[j]*i]=0; break;}}sum[i]=sum[i-1]+mobius[i];}
}int main()
{pre();int T; int a,b,d;scanf("%d",&T);while(T--){int ans=0;scanf("%d%d%d",&a,&b,&d);a/=d; b/=d;int l,r;int limit=min(a,b);for(l=1;l<=limit;l=r+1){r=min(a/(a/l),b/(b/l));ans+=(sum[r]-sum[l-1])*(a/l)*(b/l);}printf("%d\n",ans);}return 0;
}
