C. Vika and Price Tags
대회때 풀었던 문젠데 에디토리얼을 살펴보려한다.
ai=bi 를 그냥 a,b 라고 하자.
a=b=0 이라면 모두 0이여서 신경쓸 필요 없다.
a=b 라면 a,b,0,b,b,0,⋯ 처럼 0이 나온다.
a≥b 라면 한 번의 연산 이후에는 b,a−b 가 되고 이것의 합이 a 라서 a′+b′ 의 합이 줄어든다.
a<b 라면 두 번의 연산 이후에는 b−a,a 가 되고 이것의 합이 b 라서 a′+b′ 의 합이 줄어든다.
수가 유한히 감소할 수 있으므로 언젠가 0이 됨을 알 수 있다.
처음 0이 되는 순간까지 필요한 연산의 횟수를 c라 하자.
결국 0,x,x,0,x,x,0,x,x,0,⋯ 처럼 되기때문에 주기 3이 중요하다.
따라서 a=b=0 인 케이스를 제외한 모든 c가 3에 대한 동일한 나머지를 가져야 가능하다.
Solution 1
wlog.a≥b 라 하고 그렇지 않다면 연산 한 번을 진행해서 b,b−a 를 만들어 a≥b 라고 하자.
연산의 진행을 본다.
a, b, a−b, a−2b, b, a−3b, a−4b, ⋯, 처럼 진행된다.
이러한 규칙을 통해 a=kb+r(k≥0,0≤r<k) 이라 하면 일반화된 유클리드 알고리즘으로 해결가능하다.
a, b, a−b, a−2b, b, a−3b, a−4b, ⋯,a−kb,r 이 되는 시점을 본다.
k 에 따라 a−kb 가 언제 나오는지 보자(0-index).
k |
처음 나오는 곳 |
1 |
2 |
2 |
3 |
3 |
5 |
4 |
6 |
5 |
8 |
6 |
9 |
… |
|
k가 홀수라면 그 다음수가 a−(k+1)b 인데 이는 0 이하이므로 처음 나오는곳 바로 이전이 b 임을 이용해
f(b,a % b) 를 호출한다.
k가 짝수라면 그 다음수가 b 라 f(a % b,b) 를 호출한다.
두 경우 모두 진행된 횟수는 k+⌊2k⌋ 만큼 진행된다.
예를 들어, k=3 이라면 4 만큼 진행되었고 현재 b,a % b 가 나오는게 맞기 때문이다.
int gcd(int a, int b) {
if (a == 0) return 0;
if (b == 0) return 1;
if (a == b) return 2;
if (a > b) {
int q = a / b;
int r = a % b;
if (q % 2 == 1) {
return gcd(b, r) + q + q / 2;
} else {
return gcd(r, b) + q + q / 2;
}
} else {
return gcd(b, abs(b - a)) + 1;
}
}
void solve() {
int n;
cin >> n;
vi a(n), b(n);
fv(a);
fv(b);
vi g(3);
debug(1);
for (int i = 0; i < n; i++) {
if (a[i] == 0 && b[i] == 0) continue;
g[gcd(a[i], b[i]) % 3]++;
}
for (int i = 0; i < 3; i++)
if (g[i] == acc(g)) {
cout << "YES\n";
return;
}
cout << "NO\n";
}
Solution 2
아마 대회중에 내가 풀었던 방법이 이거인것같다.

Comments