C. Maximum Set

단순히 ll에 대해 l,2l,4l,8l,…l, 2l, 4l, 8l, \dots 를 검사한다.

rr 을 넘어가기 직전이 최대로 얻을 수 있는 개수이다.

그런데 첫 예시를 보면 알 수 있듯 l,3l,6l,…l,3l,6l,\dots 같은 경우도 배제할 수 없다.

그러나 그 다음에 44 이상이 곱해질일은 절대없다.

그러면 22를 두 번 곱하는 걸로 대체되어 집합의 원소 개수가 더 늘어나기 때문이다.

한가지 더, 33은 두 번 곱해질 일이 없다.

33이 곱해지는 타이밍은 상관이 없다.

1,3,6,12,…1,3,6,12,\dots이든 1,2,6,12,…1,2,6,12,\dots든 똑같다.

33이 두 번이상 곱해지면 1,3,9,181,3,9,18가 되어 1,2,4,81,2,4,8 이 되어서 22를 계속 곱한것보다 원소수가 같아질 일이 없다.

33을 두 번 곱한것보다 22를 세 번 곱한것이 더 수가 안커지고 집합 원소 개수가 늘어나기 때문이다.

따라서 [l,r][l, r]에서 먼저 22만 계속 곱해서 최대 개수가 나오는 범위 [l,k1][l, k_1]를 찾은다음에

거기서 33을 한 번 곱해도 최대 개수가 나오는 범위 [l,k2][l, k_2] 를 찾는다.

정답 집합의 개수가 SS라면 S−1S-1번의 연산중에 33을 끼워넣거나 아니면 22 만 써서 할 수 있으므로

S(k2−l+1)+(k1−k2)S(k_2-l+1) + (k_1-k_2) 가 정답이다.

void solve() {
   int l, r;
   cin >> l >> r;
 
   auto C = [&](int i) {
      int ret = 0;
      int c = i;
      while (c <= r) {
         ret++;
         c *= 2;
      }
      return ret;
   };
   auto C3 = [&](int i) {
      int ret = 0;
      int c = i;
      while (c <= r) {
         ret++;
         if (i == c) c *= 3;
         else c *= 2;
      }
      return ret;
   };
 
   int ans1 = C(l), ans2 = 0;
   cout << ans1 << ' ';
 
   int lo = l, hi = r, ret3 = -1, ret2 = -1;
   while (lo <= hi) {
      int m = lo + hi >> 1;
      if (C3(m) == ans1) ret3 = m, lo = m + 1;
      else hi = m - 1;
   }
   lo = l, hi = r;
   while (lo <= hi) {
      int m = lo + hi >> 1;
      if (C(m) == ans1) ret2 = m, lo = m + 1;
      else hi = m - 1;
   }
   if (ret3 == -1) {
      cout << ret2 - l + 1;
   } else {
      int cnt3 = ret3 - l + 1;
      int cnt2 = ret2 - l + 1 - cnt3;
 
      ans2 = cnt2;
      ans2 = md(ans2 + ans1 * cnt3);
      cout << ans2;
   }
   cout << endl;
}

Comments

You may also enjoy