# [题解] Luogu – 2247 YY的GCD

### 输出格式

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

### 样例输入

2
10 10
100 100


### 样例输出

30
2791


### 解题思路

$$\sum_{i=1}^n \sum_{j=1}^m \boldsymbol{f}(gcd(i, j))$$

$$\boldsymbol{f}(x) = \begin{cases} 1 & n 是质数 \\ 0 & n 不是质数 \end{cases}$$

$$\boldsymbol{f} = \boldsymbol{1} * \boldsymbol{g}$$

$$\boldsymbol{g} = \boldsymbol{\mu} * \boldsymbol{f}$$

$$\boldsymbol{g}(n) = \sum_{p \mid n} \boldsymbol{\mu}(\frac{x}{n})$$

$$\sum_{i=1}^n \sum_{j=1}^n \sum_{d \mid gcd(i, j)} \boldsymbol{g}(d)$$

\begin{aligned} & \sum_{i=1}^n \sum_{i=1}^m \sum_{d \mid i, d \mid j} \boldsymbol{g}(d) \\ & = \sum_{d=1}^{\min(n, m)} \boldsymbol{g}(d) \sum_{i=1}^n \sum_{j=1}^m [d \mid i] [d \mid j] \\ & = \sum_{d=1}^{\min(n, m)} \boldsymbol{g}(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \end{aligned}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 10000000 + 10;
const int SIZ = 10000000;

inline int read(){
int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9')
ch = getchar();

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

int mu[MAXN], prime[MAXN], g[MAXN], cnt;
long long sum[MAXN];

bool isPrime[MAXN];

inline void init(){
mu[1] = 1;
for(register int i=2; i<=SIZ; i++){
if(!isPrime[i]){
prime[++cnt] = i;
mu[i] = -1;
}

for(register int j=1; j<=cnt; j++){
if(i * prime[j] > SIZ)
break;

isPrime[i * prime[j]] = true;

if(i % prime[j] == 0){
mu[i * prime[j]] = 0;
break;
}else{
mu[i * prime[j]] = -mu[i];
}
}
}

for(register int i=1; i<=cnt; i++){
int p = prime[i];
for(register int j=1; j * p <= SIZ; j++){
g[j * p] += mu[j];
}
}

for(register int i=1; i<=SIZ; i++){
sum[i] = sum[i-1] + g[i];
}
}

long long ans;

inline void solve(int n, int m){
ans = 0;
for(register int i=1, j; i<=min(n, m); i = j + 1){
j = min(n/(n/i), m/(m/i));
ans += 1LL * (n/i) * (m / i) * (sum[j] - sum[i-1]);
}
}

int T, n, m;

int main(){
init();

T = read();

while(T--){
n = read();
m = read();

solve(n, m);

printf("%lld\n", ans);
}

return 0;
}