链接:lg3327
题解
- $ans=\sum_{i}^n{\sum_{j}^m{gcd(i,j)=p}}$
- $ans=\sum_{d \in p}^{}{\sum_{i}^{\frac nd}{\sum_{j}^{\frac md}{\sum_{x|gcd(i,j)}^{}{\mu(x)}}}}$
- $ans=\sum_{d \in p}^{}{\sum_{x}^{min(\frac nd,\frac md)}{\mu(x)[\frac n{dx}][\frac m{dx}]}}$
- 换一个枚举项,枚举dx
- $ans=\sum_{T}^{min(n,m)}{\sum_{x|T}^{}{\mu(\frac Tx)[\frac nT][\frac mT]}}$
- $ans=\sum_{T}^{min(n,m)}{[\frac nT][\frac mT]\sum_{x|T}^{}{\mu(\frac Tx)}}$
- 显然这里就可以O($\sqrt n$)做了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
const int N=1e7+7;
int n,m,p[N],cnt,vis[N],mu[N],g[N],T,l,r;
ll ans,sum[N];
void get_mu(int n){
mu[1]=1;
rep(i,2,n){
if(!vis[i])mu[i]=-1,p[++cnt]=i;
for(int j=1;j<=cnt&&i<=n/p[j];++j){
vis[i*p[j]]=1;
if(i%p[j]==0)break;
mu[i*p[j]]-=mu[i];
}
}
rep(j,1,cnt)for(int i=1;i<=n/p[j];++i)g[i*p[j]]+=mu[i];
rep(i,1,n)sum[i]=sum[i-1]+(ll)g[i];
}
int main(){
scanf("%d",&T);
get_mu(N-7);
while(~scanf("%d%d",&n,&m)){
ans=0;l=1;
int len=min(n,m);
while(l<=len){
r=min(n/(n/l),m/(m/l));
ans+=(ll)(n/l)*(m/l)*(sum[r]-sum[l-1]);
l=r+1;
}
printf("%lld\n",ans);
}
return 0;
}