Educational Codeforces Round 144 (Rated for Div. 2) - C. Maximum Set (1600)

C. Maximum Set

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

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

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

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

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

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

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

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

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

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

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

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

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

$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;
}