BOJ 14252 - 공약수열

BOJ 14252 - 공약수열

항상 $a, b~(a<b)$ 의 사이에서 $gcd(a,x)=1 ~\&~ gcd(b,x)=1$ 을 만족시키는 $x$는 두개 이하로 추가해줄 수 있다.

이걸 증명하는건 어렵다는데, 적당히 직감으로 풀면 된다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   sort(all(a));
   debug(a);

   vi add(n);
   int ans = 0;
   for (int i = 0; i < n - 1; i++) {
      if (gcd(a[i], a[i + 1]) != 1) {
         int f = 0;
         for (int j = a[i] + 1; j < a[i + 1]; j++) {
            if (gcd(j, a[i]) == 1 && gcd(j, a[i + 1]) == 1) {
               f = 1;
               break;
            }
         }
         if (f) ans++;
         else ans += 2;
      }
   }
   cout << ans;
}