C. Vika and Price Tags

대회때 풀었던 문젠데 에디토리얼을 살펴보려한다.


ai=bia_i=b_i 를 그냥 a,ba,b 라고 하자.

a=b=0a=b=0 이라면 모두 00이여서 신경쓸 필요 없다.

a=ba=b 라면 a,b,0,b,b,0,a,b,0,b,b,0,\cdots 처럼 00이 나온다.

aba \ge b 라면 한 번의 연산 이후에는 b,abb, a-b 가 되고 이것의 합이 aa 라서 a+ba'+b' 의 합이 줄어든다.

a<ba < b 라면 두 번의 연산 이후에는 ba,ab-a, a 가 되고 이것의 합이 bb 라서 a+ba'+b' 의 합이 줄어든다.

수가 유한히 감소할 수 있으므로 언젠가 00이 됨을 알 수 있다.

처음 00이 되는 순간까지 필요한 연산의 횟수를 cc라 하자.

결국 0,x,x,0,x,x,0,x,x,0,0,x,x,0,x,x,0,x,x,0,\cdots 처럼 되기때문에 주기 33이 중요하다.

따라서 a=b=0a=b=0 인 케이스를 제외한 모든 cc33에 대한 동일한 나머지를 가져야 가능하다.

Solution 1

wlog.abwlog. a \ge b 라 하고 그렇지 않다면 연산 한 번을 진행해서 b,bab, b-a 를 만들어 aba \ge b 라고 하자.

연산의 진행을 본다.

a, b, ab, a2b, b, a3b, a4b, ,a,~b,~a-b,~a-2b,~b,~ a-3b,~ a - 4b,~ \cdots , 처럼 진행된다.

이러한 규칙을 통해 a=kb+r(k0,0r<k)a=kb+r \quad (k \ge 0, 0 \le r < k) 이라 하면 일반화된 유클리드 알고리즘으로 해결가능하다.

a, b, ab, a2b, b, a3b, a4b, ,akb,ra,~b,~a-b,~a-2b,~b,~ a-3b,~ a - 4b,~ \cdots , a-kb, r 이 되는 시점을 본다.

kk 에 따라 akba-kb 가 언제 나오는지 보자(0-index).

k 처음 나오는 곳
1 2
2 3
3 5
4 6
5 8
6 9
 

kk가 홀수라면 그 다음수가 a(k+1)ba-(k+1)b 인데 이는 00 이하이므로 처음 나오는곳 바로 이전이 bb 임을 이용해

f(b,a % b)f(b, a ~ \% ~ b) 를 호출한다.

kk가 짝수라면 그 다음수가 bbf(a % b,b)f(a ~ \% ~ b, b) 를 호출한다.

두 경우 모두 진행된 횟수는 k+k2k+\left\lfloor \dfrac{k}{2} \right\rfloor 만큼 진행된다.

예를 들어, k=3k=3 이라면 44 만큼 진행되었고 현재 b,a % bb, 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

아마 대회중에 내가 풀었던 방법이 이거인것같다.

image.png

Comments