BZOJ 2820 YY 的 GCD

根据先人总结的 gcd 反演题套路，设 f(x)=n∑i=1m∑j=1[gcd(i,j)=x],F(x)=∑x|if(i)=⌊nx⌋⌊mx⌋。
那么题目变成了询问 ∑p∈Pf(p)，其中 P 表示全体正素数构成的集合。

∑p∈Pf(p)=∑p∈P∑p|iμ(ip)F(i)=min(n,m)∑i=1∑p|i,p∈Pμ(ip)⌊ni⌋⌊mi⌋

然后预处理 sumi=i∑j=1∑p|j,p∈Pμ(jp)，对于后面那个东西数论分块即可。

代码：

#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);
    }
}