```cpp
phi[1] = 1;
int cnt = 0;
for(int i = 2; i <= M; i++){
if(fc[i] == 0){
fc[i] = i;
prime[++cnt] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt; j++){
if(prime[j] * i > M || fc[i] < prime[j]) break;
phi[i * prime[j]] = (i % prime[j] ? phi[prime[j]] * phi[i] : prime[j] * phi[i]);
fc[i * prime[j]] = prime[j];
}
}
for(int i = 1; i <= M; i++){
sum[i] = sum[i - 1] + phi[i];
}
int N;
cin >> N;
while(N--){
int a, b, d;
cin >> a >> b >> d;
int mx1 = a / d;
int mx2 = b / d;
int ans = sum[mx1] + sum[mx2] - 1;
cout << ans << sda;
}
```
代码如上，类似P2398的思路
by Epochephemeral @ 2021-05-28 16:21:08
@[hukua](/user/425544) 你代码中 `sum[mx1]+sum[mx2]` 的值等于
$\sum\limits_{i=1}^{mx_1}\sum\limits_{j=1}^{mx_1}[\gcd(i,j)==1]+\sum\limits_{i=1}^{mx_2}\sum\limits_{j=1}^{mx_2}[\gcd(i,j)==1]$
再看看，这和你需要求的一样吗？
by LeavingZ @ 2021-05-28 16:40:51
你需要求的应该是
$\sum\limits_{i=1}^{mx_1}\sum\limits_{j=1}^{mx_2}[\gcd(i,j)==1]$
by LeavingZ @ 2021-05-28 16:42:42
@[Epochephemeral](/user/425544)
$\Sigma$ 的上界不一样，没法求
by Link_Cut_Y @ 2022-07-21 17:33:13
@[Mount_](/user/519384) 捉lcy
by Lagerent @ 2022-11-24 17:03:42