首页 > 其他分享 >Lucky Chains(最大公约数的应用)

Lucky Chains(最大公约数的应用)

时间:2022-12-14 12:34:54浏览次数:73  
标签:std return gcd int res Lucky 最大公约数 primes Chains

题目:Lucky Chains

题意:
给定两个正整数a, b,若(a, b) = (a + 1, b + 1) = (a + 2, b + 2) = ... = (a + k, b + k) = 1,求 k 的最大值(k 的最大值可能为正无穷)

思路:由于最大公约数基础性质:\(gcd(a,b)=gcd(a,b-a)\)(当b > a时),我们可以推出:
\(gcd(a+k,b+k)=gcd(a+k,b-a)\)

注意到 b - a 为一个定值,由于\(b-a<=1e7\)我们可以在\(O(\sqrt{1e7})\)的时间内找出它的所有质因子,然后我们可以枚举 b - a 的所有质因子 p,
当\(gcd(a+t,p)>1\),即\(p|(a+t)\),k的最终取值为所有 t 的取值的最小值(从 0 到 t - 1,长度为 t),显然,t 的计算方法为\(p-a%p\),由于 a 可能时 p 的倍数,此时的结果因为 0,
因此 t 最终的计算方法为\((p-a\%p)\%p\)

由于有 1e6 组测试数据,所以时间复杂度为\(O(1e6*\sqrt{1e7})\),这显然会超时,超时代码如下:

#include <bits/stdc++.h>
 
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
void solve() {
    int a, b;
    scanf("%d%d", &a, &b);
    if (gcd(a, b) > 1) {
        printf("0\n");
        return;
    }
    if (a > b) {
        std::swap(a, b);
    }
    if (b == a + 1) {
        printf("-1\n");
        return;
    }
    b -= a;
    std::vector<int> primes;
    auto getPrimes = [&]() -> void {
        int tt = b;
        for (int i = 2; i <= tt / i; ++i) {
            if (tt % i == 0) {
                while (tt % i == 0) {
                    tt /= i;
                }
                primes.push_back(i);
            }
        }
        if (tt > 1) {
            primes.push_back(tt);
        }
    };
    getPrimes();
 
    int res = 1e9;
    for (auto p : primes) {
        int k = (a / p + 1) * p - a;
        res = std::min(res, k);
    }
    printf("%d\n", res);
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
 
    return 0;
}

考虑对上述做法进行优化,我们直到线性筛法可以保证每一个合数只会被它的最小素因子筛掉,因此我们可以考虑在线性筛的过程中开一个数组 mp 来记录每一个数的最小质因子
我们先花去\(O(1e7)\)的时间筛出每一个数的最小素因子,然后对于每一次询问迭代的求出 a 的所有素因子,同时对结果进行计算,每次查询的时间复杂度不超过\(O(log(1e7))\),这样就可以通过本问题:

AC程序:

#include <bits/stdc++.h>
 
constexpr int N = 1e7;
int mp[N + 5];  // 存储每一个数的最小质因子
std::vector<int> primes;
 
void solve() {
    int a, b;
    std::cin >> a >> b;
    b -= a;
 
    if (b == 1) {
        std::cout << -1 << '\n';
        return;
    }
 
    int res = 1e9;
    while (b > 1) {
        int p = mp[b];
        b /= p;
        res = std::min(res, (p - a % p) % p);
    }
 
    std::cout << res << '\n';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    // 筛出每个数的最小质因子
    for (int i = 2; i <= N; ++i) {
        if (!mp[i]) {
            mp[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; primes[j] <= N / i; ++j) {
            mp[primes[j] * i] = primes[j];
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
 
    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
 
    return 0;
}

标签:std,return,gcd,int,res,Lucky,最大公约数,primes,Chains
From: https://www.cnblogs.com/hacker-dvd/p/16981728.html

相关文章