题目传送门

题解

不多说,上式子
$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}isprime[gcd(i, j)]$

下文$isprime$简写成$is$

默认n<m,如果不是请swap(n, m)

枚举gcd为d

$\sum\limits_{d=1}^{n}is[d]\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i, j)\;=\;\;\;d]$

除d

$\sum\limits_{d=1}^{n}is[d]\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i, j)\; = \;\;\; 1]$

反演

$\sum\limits_{d=1}^{n}is[d]\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{p\mid gcd(i, j)}\mu(p)$

把p放前面枚举

$\sum\limits_{d=1}^{n}is[d]\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{n}{dp}\rfloor$

令Q = dp,枚举Q

$\sum\limits_{Q=1}^{n}\lfloor\frac{n}{dp}\rfloor\lfloor\frac{n}{dp}\rfloor\sum\limits_{d\mid Q}is[d]\;\;\times\;\;\mu(\frac{Q}{d})$

设$f(x) = \sum\limits_{d\mid Q}is[d]\;\;\times\;\;\mu(\frac{x}{d})$

上面的f可以线性筛也可以$n\times \;\;\ln n$暴力得出,然后分段求和就好

附代码 上面暴力,下面线筛f

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int N = 10001000;bool vis[N];int pr[N>>1], f[N], mu[N], tot, sum[N];void init() { mu[1] = 1; for(int i = 2; i < N; i ++ ) { if(!vis[i]) {pr[++tot] = i, mu[i] = -1;} for(int j = 1; j <= tot && pr[j]*i < N; j ++ ) { vis[i*pr[j]] = 1; if(i%pr[j] == 0) break; mu[i*pr[j]] = -mu[i]; } } for(int i = 1; i <= tot; i ++ ) for(int j = 1; pr[i]*j < N; j ++ ) f[pr[i]*j]+=mu[j]; for(int i = 1; i < N; i ++ ) sum[i] = sum[i-1] + f[i];}int main() { init(); int T; scanf("%d", &T); while(T--) { int n, m; scanf("%d%d", &n, &m); if(n > m) swap(n, m); int lst; ll ans = 0; for(int i = 1; i <= n; i = lst+1) { lst = min(n/(n/i), m/(m/i)); ans += ((ll)sum[lst]-sum[i-1])*(n/i)*(m/i); } printf("%lld\n", ans); }}
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 11000000;bool np[N+10];int mu[N+10], tot, pr[N+10], sum[N+10];int f[N+10];int t, n, m;void init() { mu[1]=1; for(int i=2;i<=N;i++) { if(!np[i]) { pr[++tot]=i; mu[i]=-1; f[i]=1; } for(int j=1;j<=tot&&i*pr[j]<=N;j++) { np[i*pr[j]]=1; if(!(i%pr[j])) { mu[i*pr[j]]=0; f[i*pr[j]]=mu[i]; break; } mu[i*pr[j]]=-mu[i]; f[i*pr[j]]=mu[i]-f[i]; } sum[i]=sum[i-1]+f[i]; }}void solve(int n, int m) { if(n>m)swap(n,m); int lst; long long ans=0; for(int i=1;i<=n;i=lst+1) { lst = min(n/(n/i), m/(m/i)); ans+=1ll*(sum[lst]-sum[i-1])*(n/i)*(m/i); } printf("%lld\n", ans);}int main() { init(); scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); solve(n,m); }}