即求：

$$\sum_{i=1}^{N}\limits{\sum_{j=1}^{M}\limits{[\text{gcd}(i, j)\in \text P]}}$$ 其中$\text P$为质数集。

推导过程如下：

$$\sum_{i=1}^{N}\limits{\sum_{j=1}^{M}\limits{[\text{gcd}(i, j)\in \text P]}}$$$$\sum_{p \in \text{P}}\limits{\sum_{i=1}^{N}\limits{\sum_{j=1}^{M}\limits{[\text{gcd}(i, j) = p]}}}$$$$\sum_{p \in \text{P}}\limits{\sum_{i=1}^{\lfloor \frac{N}{p} \rfloor}\limits{\sum_{j=1}^{\lfloor \frac{M}{p} \rfloor}\limits{[\text{gcd}(i, j) = 1]}}}$$$$\sum_{p \in \text{P}}\limits{\sum_{i=1}^{\lfloor \frac{N}{p} \rfloor}\limits{\sum_{j=1}^{\lfloor \frac{M}{p} \rfloor}\limits{\sum_{d|i, d|j}\limits{\mu(d)}}}}$$$$\sum_{p \in \text{P}}\limits{\sum_{d=1}^{\frac{\text{min}(N, M)}{p}}\limits{\mu(d) \times \lfloor \frac{N}{pd} \rfloor \lfloor \frac{M}{pd} \rfloor}}$$

设$t = pd$：$$\sum_{p \in \text{P}}\limits{\sum_{d=1}^{\frac{\text{min}(N, M)}{p}}\limits{\mu(d) \times \lfloor \frac{N}{t} \rfloor \lfloor \frac{M}{t} \rfloor}}$$

$$\sum_{t=1}^{\text{min}(N, M)}\limits{\lfloor \frac{N}{t} \rfloor \lfloor \frac{M}{t} \rfloor \sum_{d \in \text{P},d|t}\limits{\mu(\frac{t}{d})}}$$

设$$F(x)=\sum_{d \in \text{P},d|x}\limits{\mu(\frac{x}{d})}$$

可以看出， 可以使用数论分块解决问题，数论分块的要求就是函数$F(x)$可以求出前缀和。只需要求出其前缀和即可。可以考虑枚举每一个质数的倍数。

void euler1(int n){
    for(int i = 1;i <= tot;i++){
        for(int j = prime[i];j <= n;j += prime[i]){
            F[j] += mu[j / prime[i]];
        }
    }
}

注意

预处理$\mu(x)$时，一定记住给$\mu(1)$赋值为$1$。

code

int prime[_];
int not_prime[_], tot = 0;
int mu[_];
void euler0(int n){
    mu[1] = 1;
    for(int i = 2;i <= n;i++){
        if(!not_prime[i]) prime[++tot] = i, mu[i] = -1;
        for(int j = 1;j <= tot && prime[j] * i <= n;j++){
            not_prime[prime[j] * i] = 1;
            if(i % prime[j] != 0) mu[i * prime[j]] = -mu[i];
            else { mu[prime[j] * i] = 0; break; }
        }
    }
}
int F[_];
void euler1(int n){
    for(int i = 1;i <= tot;i++){
        for(int j = prime[i];j <= n;j += prime[i]){
            F[j] += mu[j / prime[i]];
        }
    }
}
signed main()
{
#ifdef LOCAL_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    clock_t c1 = clock();
    euler0(1e7 + 10); euler1(1e7 + 10);
    for(int i = 1;i <= int(1e7 + 10);i++) F[i] += F[i - 1];
//    for(int i = 1e7;i <= int(1e7 + 10);i++) printf("%d%c", F[i], " \n"[i == 20]);
    int T = read();
    while(T--){
        int N = read(), M = read(), _n = min(N, M);
        long long  ans = 0;
        for(int i = 1;i <= _n;){
            int L = i, x0 = N / L, x1 = M / L;
            int R = min(N / x0, M / x1);
            ans += 1LL * (x0 *1ll* x1) * (F[R] - F[L - 1]);

            i = R + 1;
        }
        printf("%lld\n", ans);
    }
    std::cerr << "\n\nTime:  " << clock() - c1 << "  ms" << std::endl;
    return 0;
}