跳转至

Lucky Chains

Lucky Chains

题意

给一对数 \((x,y)\)，找到最小的 \(k(k\ge 0)\) 满足 \(\gcd(x+k,y+k)\ne 1\)。

⭐rating: 1600

分析

令 \(\gcd(x+k,y+k)=g\)，那么 \((y+k)-(x+k)=y-x\) 同样也可以被 \(g\) 整除，就是说 \(\gcd(x+k,y-x)=h\) 可以被 \(g\) 整除；回到 \(\gcd(x+k,y-x)=h\) 那么 \((x+k)+(y-x)=y+k\) 也可以被 \(h\) 整除，那么 \(\gcd(x+k,y+k)=g\) 可以被 \(h\) 整除。

由于 \(h|g\) 和 \(g|h\)，可以推出 \(g=h\)。

题目就变成找到最小的 \(k\) 满足 \(\gcd(x+k,y-x)\ne 1\)。

我们可以找到 \(y-x\) 所有的质因数 \(p\)，以求得最小的 \(x+k\) 满足 \(p|x+k\)。

可以证明得出 \(n\) 里面所有的质因数小于 \(\log_2n\) 个。

通过修改 Eratosthenes 筛法可以取得对于一个数 \(k\)，它的最小质因数为 \(mind[k]\)。时间复杂度为 \(O(n\log\log n)\) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void Ethe(int n) {
    // 首先等于自己
    for (int i = 1; i < n; i++)
        mind[i] = i;

    for (int p = 2; p < n; p++) {
        // 不是质数
        if (mind[p] != p)
            continue;
        // 是质数
        for (int d = 2 * p; d < n; d += p)
            mind[d] = min(mind[d], p); // 取最小的质数
    }
}

假设当前的数为 \(k_1=2*2*2*5=40\) - \(p_1=mind[k_1=40]=2\)，此时 \(k_2=\frac{k_1}{p_1}=20\) - \(p_2=mind[k_2=20]=2\)，此时 \(k_3=\frac{k_2}{p_2}=10\) - \(p_3=mind[k_3=10]=2\)，此时 \(k_4=\frac{k_3}{p_3}=5\) - \(p_1=mind[k_4=5]=5\)，此时 \(k_5=\frac{k_4}{p_4}=1\)

时间复杂度为 \(k\) 内质因数的个数，\(O(\log k)\)

最后总时间复杂度为预处理 \(O(n\log\log n)\) \(+\) 计算 \(y-x\) 中质数个数 \(O(\log (y-x))\)

代码

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

const int N = int(1e7) + 5;
const int inf = 0x3f3f3f3f;

int mind[N];

void Ethe(int n) {
    for (int i = 1; i < n; i++)
        mind[i] = i;

    for (int p = 2; p < n; p++) {
        if (mind[p] != p)
            continue;
        for (int d = 2 * p; d < n; d += p)
            mind[d] = std::min(mind[d], p);
    }
}

std::vector<int> get_primes(int v) {
    std::vector<int> rs;
    while (v > 1) {
        if (rs.empty() || rs.back() != mind[v])
            rs.push_back(mind[v]);
        v /= mind[v];
    }
    return rs;
}

void solve() {
    int x, y;
    std::cin >> x >> y;

    int d = y - x;
    if (d == 1) {
        std::cout << -1 << std::endl;
        return;
    }

    int res = inf;
    for (int &p : get_primes(d))
        res = std::min(res, (x + p - 1) / p * p);
    std::cout << res - x << std::endl;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    Ethe(N); // init

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}
回到页面顶部