C. Candy Store

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

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

ci=bi⋅dic_i=b_i \cdot d_i 이므로 bi∣cib_i \mid c_i 이므로 가능한 구간에서 lcm(bi,bi+1,… )∣clcm(b_i, b_{i+1}, \dots) \mid c 여야 한다.

di∣aid_i \mid a_i 이므로 c=bi⋅di∣ai⋅bic=b_i \cdot d_i \mid a_i \cdot b_i 이고 결국 위에서 구한 cc가 ai⋅bia_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;
}

Comments

You may also enjoy