題意：求$\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^M {f(i,j)} } $，其中f(i,j)=(0,0)與(i,j)連線上點的數量
題解：
如果一個點(x',y')在(0,0)與(x,y)的連線上，則有gcd(x',y')==gcd(x,y)。因此f(i,j)=(gcd(i',j')=gcd(i,j))且i'<i,j'<j的點的數量。
由于題目中不需要統計(x,y)本身，所以計算出的2*ans=ANS+N*M=>ANS=2*ans-N*M。
現在我們來看如何求ans，我們枚舉倍數i，則滿足x%i==0 && y%i==0的點(x,y)的數量就有(N/i)*(M/i)個，而對于每個這樣的點，其與(0,0)連線上的點就有phi(i)個，因此
ans=sum(phi(i)*(N/i)*(M/i))
然后用分塊就可以將復雜度降為sqrt(N)
#include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; #define ll long longconst int MAXN=100000+2; ll N,M,ans; ll f[MAXN]; ll phi[MAXN],prime[MAXN]; bool flag[MAXN];int main(){cin >> N >> M;if(M>N) swap(N,M);phi[1]=1;for(int i=2,k=0;i<=n;i++){if(!flag[i]) prime[++k]=i,phi[i]=i-1;for(int j=1;j<=k && prime[j]*i<=n;j++){flag[i*prime[j]]=1;if(!(i%prime[j])){phi[i*prime[j]]=phi[i]*prime[j];break;}phi[i*prime[j]]=phi[i]*(prime[j]-1);}}for(int i=2;i<=M;i++) phi[i]+=phi[i-1];for(int i=1,j;i<=M;i=j+1){j=min(N/(N/i),M/(M/i));ans+=(phi[j]-phi[i-1])*(N/i)*(M/i);}cout << 2*ans-N*M << endl;return 0; }
?
)
