题解 SP4491 【PGCD - Primes in GCD Table】
HohleFeuerwerke
·
·
题解
前言
原题，YY的GCD。
正文
\sum_{i=1}^N\sum_{j=1}^M[\gcd(i,j)\in prime]
设 N\leq M。
设出来：f(x)=\begin{cases}0\ \ (x\in prime)\\1 \ \ (x\notin prime)\end{cases} 所以设 1*f=g，g=f*\mu。
g(x)=\sum_{d|x}f(d)\mu(\frac{x}{d})
然后可以小细节：d 不是素数的时候没有贡献，所以 g(x)=\sum_{p|x}\mu(\frac{x}{p})。
\sum_{i=1}^N\sum_{j=1}^Mf(\gcd(i,j))&=\sum_{i=1}^N\sum_{j=1}^M\sum_{d|i,d|j}g(d)\\
&=\sum_{d=1}^Ng(d)\sum_{i=1}^N\sum_{j=1}^M1\\
&=\sum_{d=1}^{N}g(d)\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor
\end{aligned}
总复杂度 $\Theta(n\log n+T\sqrt n)$。
```cpp
#include<bits/stdc++.h>
#define HohleFeuerwerke using namespace std
#pragma GCC optimize(3,"Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
//#define int long long
HohleFeuerwerke;
inline int read(){
int s=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) s=s*10+c-'0';
return s*f;
}
inline void write(long long x){
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar('0'+x%10);
}
const int MAXN=1e7+5;
int T,N,M;
int mu[MAXN],pri[MAXN],g[MAXN],tot;
int Gsum[MAXN];
bool ispri[MAXN];
inline void init_Mu(){
ispri[1]=mu[1]=true;
for(int i=2;i<=MAXN-5;i++){
if(!ispri[i]) pri[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&i*pri[j]<=MAXN-5;j++){
ispri[i*pri[j]]=true;
if(i%pri[j]) mu[i*pri[j]]=-mu[i];
else{mu[i*pri[j]]=0;break;}
}
}
}
inline void init_G(){
for(int j=1;j<=tot;j++)
for(int i=1,p=pri[j];i*pri[j]<=MAXN-5;i++)
g[i*p]+=mu[i];
for(int i=1;i<=MAXN-5;i++) Gsum[i]=Gsum[i-1]+g[i];
}
inline long long solve(){
long long ans=0;
N=read(),M=read();
if(N>M) swap(N,M);
for(int l=1,r;l<=N;l=r+1){
r=std::min(N/(N/l),M/(M/l));
ans+=(long long)(Gsum[r]-Gsum[l-1])*(long long)(N/l)*(long long)(M/l);
}
return ans;
}
signed main()
{
init_Mu();init_G();
T=read();
while(T--){
printf("%lld\n",solve());//putchar('\n');
}
}
```