题目: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