Codeforces Round 860 (Div. 2) - C. Candy Store (1700)

C. Candy Store

결국 계속 많은 그룹을 묶어야 최적이다.

$c_i$를 바로바로 결정해서 가능한지를 따지려하지말자.

$c_i=b_i \cdot d_i$ 이므로 $b_i \mid c_i$ 이므로 가능한 구간에서 $lcm(b_i, b_{i+1}, \dots) \mid c$ 여야 한다.

$d_i \mid a_i$ 이므로 $c=b_i \cdot d_i \mid a_i \cdot b_i$ 이고 결국 위에서 구한 $c$가 $a_i \cdot b_i$ 들의 GCD를 나눌 수 있는지 검사하는 문제가 된다.

void solve() {
   int n;
   cin >> n;
   vi a(n), b(n);
   for (int i = 0; i < n; i++) cin >> a[i] >> b[i], a[i] *= b[i];
 
   int ans = 0;
   for (int i = 0; i < n;) {
      int j = i;
      int L = 1, G = 0;
      while (j < n) {
         G = gcd(G, a[j]);
         L = lcm(L, b[j]);
 
         if (G % L) break;
         else j++;
      }
      i = j;
      ans++;
   }
   cout << ans << endl;
}