YY的GCD

题目大意

给定 \(N, M\) ,求 \(1<=x<=N\) , \(1<=y<=M\) 且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对?

输入格式

第一行一个整数 \(T\) 表述数据组数
接下来T行，每行两个正整数，表示 \(N, M\)

输出格式

\(T\) 行，每行一个整数表示第 \(i\) 组数据的结果

说明/提示

\(T = 10000\)
\(N, M \leq 10000000\)

解析

啊啊啊啊啊啊啊啊，这什么题？
很容易想到答案就是
\[ \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j) \in prime] \]

然后就按套路化简式子

\[ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j) \in prime] &=\sum_{k \in prime} \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=k] \\ &=\sum_{k \in prime} \sum_{k|i}^n \sum_{k|j}^m [\gcd(\frac{i}{k} , \frac{j}{k})=1] \\ &=\sum_{k \in prime} \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j)=1] \\ \end{aligned} \]
然后套入莫比乌斯的第一条性质

\[ \begin{aligned} \sum_{k \in prime} \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j)=1] &=\sum_{k \in prime} \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{k} \rfloor} \sum_{d|\gcd(i,j)} \mu(d) \\ &=\sum_{k \in prime} \sum_{d=1}^{\min (\lfloor \frac{n}{k} \rfloor , \lfloor \frac{m}{k} \rfloor)} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \end{aligned} \]
嗯，好极了
开开心心打完，\(TLE\) 了
原因，时间复杂度：\(O(\sum_{k \in prime}^n 1 * \sqrt n)\)
这是有问题的
那怎么办？
似乎没办法化简了
然而，一波骚操作来了
令\(T=kd\)，然后改为枚举 \(T\) 的形式
\[ \begin{aligned} \sum_{k \in prime} \sum_{d=1}^{\min (\lfloor \frac{n}{k} \rfloor , \lfloor \frac{m}{k} \rfloor)} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \\ &=\sum_{T=1}^{\min(n,m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{k|T,k \in prime} \mu(\frac{T}{k}) \end{aligned} \]

令 $f(T)=\sum_{k|T,k \in prime} \mu(\frac{T}{k})
噢噢噢噢噢噢噢噢，我们惊喜的发现， \(f(i)\) 可以枚举质数及其倍数预处理出来
然后数论分块
切切切切切切切切！！！

代码

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;

const int N = 1e7;
int T , n , m , mu[N + 5] , prime[N + 5] , tot , vis[N + 5];
LL f[N + 5];

inline void prepare()
{
    mu[1] = 1;
    for(register int i = 2; i <= N + 5; i++)
    {
        if (!vis[i]) mu[prime[++tot] = i] = -1;
        for(register int j = 1; j <= tot && prime[j] * i <= N + 5; j++)
        {
            vis[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
            mu[prime[j] * i] = -mu[i];
        }
    }
    for(register int i = 1; i <= tot; i++)
        for(register int j = 1; prime[i] * j <= N + 5; j++)
            f[prime[i] * j] += (LL)mu[j];
    for(register int i = 1; i <= N + 5; i++) f[i] += f[i - 1];
}

inline LL solve(int n , int m)
{
    register LL res = 0;
    register int lim = min(n , m) , j;
    for(register int i = 1; i <= lim; i = j + 1)
    {
        j = min(n / (n / i) , m / (m / i));
        res += (LL)(f[j] - f[i - 1]) * (LL)(n / i) * (LL)(m / i);
    }
    return res;
}

int main()
{
    prepare();
    scanf("%d" , &T);
    while (T--)
    {
        scanf("%d%d" , &n , &m);
        printf("%lld\n" , solve(n , m));
    }
}