TIOJ-1219

2qbingxuan

2020-02-25

TIOJ , math

發糖果囉

https://tioj.ck.tp.edu.tw/problems/1219

Description

求符合$1 \leq x \leq n, 1 \leq y \leq m$且$x,y$的最大公因數是$g$的數對有多少對
有多筆測試資料，$1 \leq n, m, g \leq 50000$

Solution

莫比烏斯反演

lemma

$$
\sum_d \mu(d) [d | x] = [x = 1]
$$
拿來簡化 $[\gcd(i,j)=1]$ 的部分，再想辦法換一下$\sum$的位置
$$
\begin{align*}
\sum _ {i=1}^n \sum _ {j=1}^m [\gcd(i, j) = g] &= \sum _ {i=1}^{\lfloor n/g \rfloor} \sum _ {j=1}^{\lfloor m/g \rfloor} [\gcd(i, j) = 1]\newline
\sum _ {i=1}^N \sum _ {j=1}^M [\gcd(i, j) = 1] &= \sum _ {i=1}^N \sum _ {j=1}^M \sum_d \mu(d) \cdot [d | \gcd(i, j)]\newline
&= \sum_d \mu(d) \sum _ {i=1}^N \sum _ {j=1}^M [d | \gcd(i, j)]\newline
&= \sum_d \mu(d) {\lfloor \frac{N}{d} \rfloor} {\lfloor \frac{M}{d} \rfloor}
\end{align*}
$$
預處理$\mu$的前綴，利用數論分塊可以做到$\mathcal{O}(N + Q \sqrt{N})$

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <vector>

const int N = 50025;
bool sv[N];
int mu[N], smu[N];
std::vector<int> prs;
inline int min(int a, int b) {return a<b?a:b;}
signed main() {
    mu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!sv[i]) prs.emplace_back(i), mu[i] = -1;
        for(int p: prs) {
            if(i*p >= N) break;
            sv[i*p] = true;
            if(i%p) {
                mu[i*p] = -mu[i];
            }else {
                mu[i*p] = 0;
                break;
            }
        }
    }
    for(int i = 1; i < N; i++) smu[i] = smu[i-1]+mu[i];
    int n, m, g;
    while(scanf("%d%d%d", &n, &m, &g), n || m || g) {
        n /= g, m /= g;
        long long ans = 0;
        for(int i = 1, j; i <= n && i <= m; i = j) {
            j = min(n/(n/i), m/(m/i))+1;
            ans += 1LL * (smu[j-1] - smu[i-1]) * (n/i) * (m/i);
        }
        printf("%lld\n", ans);
    }
}