https://www.luogu.org/problemnew/show/P2257
求 \(n,m\) 中 \(gcd(i,j)==p\) 的数对的个数
求 $\sum\limits_p \sum\limits_{i=1}{n}\sum\limits_{j=1}{m}[gcd(i,j)==p] $
由套路:
\(=\sum\limits_p \sum\limits_{k=1}^{N}\mu(k) \lfloor\frac{n}{kp}\rfloor \lfloor\frac{m}{kp}\rfloor\)
再套路:
\(=\sum\limits_p \sum\limits_{T=kp}^{N}\mu(\frac{T}{p}) \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor\)
交换求和:
\(=\sum\limits_{T=1}^{N} \sum\limits_{p|T} \mu(\frac{T}{p}) \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor\)
提T:
\(=\sum\limits_{T=1}^{N} \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor \sum\limits_{p|T} \mu(\frac{T}{p})\)
后面的式子可以预处理,方法是在筛出质数表和莫比乌斯函数表之后,枚举每个质数p,再枚举倍数k,给kp加上 \(\mu(k)\) .
前面的式子可以整除分块 \(r=min(n/(n/l),m/(m/l))\) .
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 10000000+5
/* 莫比乌斯函数筛 begin */
int mu[MAXN];
int pri[MAXN],pritop;
bool notpri[MAXN];
//pritop从1开始计数
int sumdmu[MAXN],prefixsumdmu[MAXN];
void sieve3(int n) {
notpri[1]=mu[1]=1;
for(int i=2; i<=n; i++) {
if(!notpri[i])
pri[++pritop]=i,mu[i]=-1;
for(int j=1; j<=pritop&&i*pri[j]<=n; j++) {
notpri[i*pri[j]]=1;
//略有不同
if(i%pri[j])
mu[i*pri[j]]=-mu[i];
else {
mu[i*pri[j]]=0;
break;
}
}
}
for(int j=1; j<=pritop; j++) {
for(int i=1;i*pri[j]<=n;i++){
sumdmu[i*pri[j]]+=mu[i];
}
}
for(int i=1;i<=n;i++)
prefixsumdmu[i]=prefixsumdmu[i-1]+sumdmu[i];
}
/* 莫比乌斯函数筛 end */
//整除分块,n,m版
ll aliquot_patition(int n,int m) {
ll ans=0;
int N=min(n,m);
for(int l=1,r; l<=N; l=r+1) {
r=min(n/(n/l),m/(m/l));
ans+=1ll*(n/l)*(m/l)*(prefixsumdmu[r]-prefixsumdmu[l-1]);
}
return ans;
}
int main() {
sieve3(10000000);
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
printf("%lld\n",aliquot_patition(n,m));
}
}