BOJ 28127 - 숫자탑과 쿼리

BOJ 28127 - 숫자탑과 쿼리

각 층마다 개수가 $a,a+d,a+2d+\cdots$ 처럼 증가되므로

등차수열의 합 공식인 $S_n=\dfrac{n(2a+(n-1)d)}{2}$ 임을 이용해 이분탐색으로 몇층인지와 몇번째 인지를 찾아줄 수 있다.

void solve() {
   int q;
   cin >> q;
   while (q--) {
      int a, d, x;
      cin >> a >> d >> x;

      auto check = [&](int i) {
         return x <= i * (2 * a + (i - 1) * d) / 2;
      };
      int l = 1, r = 1e6, ret = 0;
      while (l <= r) {
         int m = l + r >> 1;
         if (check(m)) ret = m, r = m - 1;
         else l = m + 1;
      }
      cout << ret << ' ' << x - (ret - 1) * (2 * a + ((ret - 1) - 1) * d) / 2 << endl;
   }
}