Codeforces 1766D
Lucky Chains
Codeforces 1766D - Lucky Chains
문제를 푸는 데 필요한 배경지식
1. 에라토스테네스의 체
문제 풀이
이하의 두 수 , 를 가지고 나열된 쌍들이 모두 서로소가 될 때 까지만 의 형태로 나열했을 때, 가장 긴 배열의 길이를 구하는 문제 입니다.
와 의 차이를 라고 하고, 의 약수 중 하나 에 대해서 다음이 성립합니다.
이므로,
가 의 배수라면, 입니다.
즉, 도 의 배수입니다. 다시 말해, 는 와 의 공약수입니다.
위 성질을 이용해서, 의 약수 들을 모두 구한 뒤에, 보다 크거나 같은 의 배수들 중 에 가장 가까운 값까지만 쌍을 나열할 수 있음을 알 수 있습니다.
또한, 의 약수들 중 합성수인 약수들은 그 약수를 구성하는 소수들 또한 의 약수가 되고, 합성수들의 배수는 소수들의 배수이기도 하므로, 의 약수들 중에서 소수인 약수들만 고려하면 됩니다.
따라서 이 문제는,
인 를 소인수분해하고,
그 소수들에 대해 의 최솟값을 구하는 문제입니다.
와 의 범위가 이하이므로, 의 범위도 이하입니다.
가능한 의 값들 중 가장 큰 값을 라고 할 때 이하의 자연수들에 대하여 시간 안에 에라토스테네스의 체를 수행하고,
이를 이용해 소인수분해를 시간 안에 수행할 수 있습니다.
소인수분해를 총 번 반복하게 되므로, 전체 시간복잡도는 로, 4초 안에 충분히 해결이 가능합니다.
풀이코드
#include <bits/stdc++.h>
#define INF 999999999999
typedef long long ll;
using namespace std;
ll tt, x, y, answer, differ;
ll sieve[10001000];
vector<ll> primes;
ll gcd(ll a, ll b) {
if(a < b) swap(a, b);
if(b == 0) return a;
return gcd(b, a % b);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
sieve[1] = -1;
for(ll i = 2; i <= 10000000; i++) {
if(sieve[i] == 0) {
sieve[i] = -1;
for(ll j = 2; i * j <= 10000000; j++) {
sieve[i * j] = i;
}
}
}
cin >> tt;
while(tt--) {
cin >> x >> y;
if(y - x == 1) {
cout << -1 << '\n';
continue;
} else if (gcd(x, y) != 1) {
cout << 0 << '\n';
continue;
}
answer = INF;
differ = y - x;
primes = vector<ll>();
while(sieve[differ] != -1) {
primes.push_back(sieve[differ]);
differ /= sieve[differ];
}
if(differ > 1) primes.push_back(differ);
for(ll i = 0; i < primes.size(); i++) {
answer = min(answer, primes[i] * ((x / primes[i]) + 1) - x);
}
cout << answer << '\n';
}
return 0;
}
시간복잡도를 계산하는 과정에서 에라토스테네스의 체에 대한 시간복잡도는 어떻게 되나요? 총 시간복잡도에는 영향이 없나요?
습관적으로 에라토스테네스의 체에 대한 시간복잡도를 빠트렸네요. 에라토스테네스의 체의 시간복잡도는 d 이하의 소수를 구할 때, 시간복잡도는 O(d log(logd))이고, 공간복잡도는 O(d)입니다. 에라토스테네스의 체에 대한 시간복잡도까지 고려하면 이 문제의 시간복잡도는 O(d log(logd) + Nlogd)가 되겠네요. 포스팅도 함께 수정했습니다.
Updated: Dec. 15, 2022, 10:55 a.m.