题解 P2257 【YY的GCD】
ShuYuMo
2020-06-10 19:47:52
即求：
$$\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)$可以求出前缀和。只需要求出其前缀和即可。可以考虑枚举每一个质数的倍数。
```cpp
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
```cpp
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;
}
```