YY的GCD 莫比乌斯反演

～～～题面～～～

题解：

$ans = \sum_{x = 1}^{n}\sum_{y = 1}^{m}\sum_{i = 1}^{k}[gcd(x, y) == p_{i}]$其中k为质数个数
　　　　$$ans = \sum_{i = 1}^{k}\sum_{x = 1}^{n}\sum_{y = 1}^{m}[gcd(x, y) == p_{i}]$$
　　　　设$f(d)$表示$x$从$1$到$n$，$y$从$1$到$m$，$gcd == d$的个数，$g(d)$表示相同条件下$d | gcd$（即$gcd$为$d$的倍数）的个数
　　　　那么$$f(d) = \sum_{x = 1}^{n}\sum_{y = 1}^{m}[gcd(x, y) == d]$$,$$g(d) = \lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor$$
　　　　因为$$g(x) = \sum_{x|d}^{min(n, m)}f(d)$$
　　　　所以反演一下。
　　　　$$f(x) = \sum_{x | d}^{min(n, m)}\mu(\frac{d}{x})g(d)$$
　　　　那么$ans = \sum_{i = 1}^{k}f(p_{i})$
　　　　$$= \sum_{i = 1}^{k}\sum_{x | d}^{min(n, m)}\mu(\frac{d}{x})g(d)$$
　　　　改成直接枚举系数
　　　　$$= \sum_{i = 1}^{k}\sum_{d = 1}^{\lfloor{\frac{min(n, m)}{p_{i}}}\rfloor}\mu(d)g(dp_{i})$$
　　　　$$= \sum_{i = 1}^{k}\sum_{d = 1}^{\lfloor{\frac{min(n, m)}{p_{i}}}\rfloor}\mu(d)\lfloor{\frac{n}{dp_{i}}\rfloor \lfloor{\frac{m}{dp_{i}}\rfloor}}$$<---枚举每个$\mu(d)分别被每个质数统计了几次$
　　　　$$= \sum_{T = 1}^{min(n, m)} \lfloor{\frac{n}{T}}\rfloor \lfloor{\frac{m}{T}}\rfloor\sum_{k|T}{\mu(\frac{T}{k})}$$<---枚举每个$\lfloor{\frac{n}{T}}\rfloor \lfloor{\frac{m}{T}}\rfloor$会给哪些$\mu$做贡献（哪些$\mu$会在某次被统计$\lfloor{\frac{n}{T}}\rfloor \lfloor{\frac{m}{T}}\rfloor$次）
　　　　然后暴力枚举质数和系数，给对应的$\mu$做贡献（质数$p_{i}$给它的倍数做贡献），统计前缀和，对前面的$\lfloor{\frac{n}{T}}\rfloor \lfloor{\frac{m}{T}}\rfloor$进行整数分块处理

#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 10000100
#define LL long long 
int n, m, tot, t;
int prime[AC], mu[AC];
LL s[AC], ans;
bool z[AC];

inline int read()
{
    int x = 0;char c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x;
}

void pre()
{
    int now;
    mu[1] = 1;
    for(R i = 2; i <= 10000000; i++)
    {
        if(!z[i]) prime[++tot] = i, mu[i] = -1;
        for(R j = 1; j <= tot; j++)
        {
            now = prime[j];
            if(i * now > 10000000) break;
            z[i * now] = true;
            if(!(i % now)) break;            
            mu[now * i] = -mu[i];
        }
    }
    int p;
    for(R i = 1; i <= tot; i++)//枚举质数 
    {
        p = prime[i];//卡常
        for(R j = p; j <= 10000000; j += p) //枚举倍数
            s[j] += mu[j / p];//or j = 系数, s[j * prime[i]] += mu[j];
    }
    for(R i = 1; i <= 10000000; i++) s[i] += s[i - 1];
}

void work()
{
    t = read();
    while(t--)
    {
        int pos = 0;
        ans = 0;
        n = read(), m = read();
        int b = min(n, m);//这里要取min！！！
        for(R i = 1; i <= b; i = pos + 1)
        {
            pos = min(n / (n / i), m / (m / i));
            ans += (LL) (n / i) * (LL) (m / i) * (LL) (s[pos] - s[i - 1]);//error 只有ans是LL是不够的
        }        
        printf("%lld\n", ans);
    }
}

int main()
{
//    freopen("in.in", "r", stdin);
    //freopen("YYnoGCD.in", "r", stdin);
    //freopen("YYnoGCD.out", "w", stdout);
    pre();
    work();
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}