BZOJ 2820.YY 的 GCD

根据先人总结的 gcd\gcd 反演题套路,设 f(x)=i=1nj=1m[gcd(i,j)=x],F(x)=xif(i)=nxmxf(x) = \sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j) = x],F(x) = \sum\limits_{x | i} f(i) = \lfloor \dfrac n x \rfloor \lfloor \dfrac m x \rfloor
那么题目变成了询问 pPf(p)\sum\limits_{p \in \mathbb P} f(p),其中 P\mathbb P 表示全体正素数构成的集合。

然后预处理 sumi=j=1ipj,pPμ(jp)sum_i = \sum\limits_{j = 1}^i \sum\limits_{p | j,p \in \mathbb P} \mu(\dfrac j p),对于后面那个东西数论分块即可。

代码:

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
43
44
45
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e7;
int t;
int cnt,prime[N + 5],vis[N + 5],mu[N + 5];
long long sum[N + 5];
int main()
{
mu[1] = 1;
for(register int i = 2;i <= N;++i)
{
if(!vis[i])
prime[++cnt] = i,mu[i] = -1;
for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
else
mu[i * prime[j]] = -mu[i];
}
}
for(register int i = 1;i <= cnt;++i)
for(register int j = 1;prime[i] * j <= N;++j)
sum[prime[i] * j] += mu[j];
for(register int i = 1;i <= N;++i)
sum[i] += sum[i - 1];
scanf("%d",&t);
int n,m;
long long ans;
while(t--)
{
ans = 0;
scanf("%d%d",&n,&m);
if(n > m)
swap(n,m);
for(register int l = 1,r;l <= n;l = r + 1)
{
r = min(n / (n / l),m / (m / l));
ans += (long long)(n / l) * (m / l) * (sum[r] - sum[l - 1]);
}
printf("%lld\n",ans);
}
}