23338번: Eatcoin

\(x\)를 먼저 구한 후, 이분탐색을 통해 \(y\)를 구한다.

 

\(\displaystyle\sum_{k=1}^{n}k^5\)은 \(O(1)\)시간에 구할 수 있다.

 

Python으로 풀면 편하다.

p, q = map(int, input().split())
def f(n):
    return n ** 2 * (2 * n ** 4 + 6 * n ** 3 + 5 * n * n - 1) // 12
i = 1
while True:
    if p <= q * i ** 5:
        x = i * p - f(i - 1) * q
        print(x)
        break
    i += 1

lo, hi = 0, 10 ** 100
while lo < hi:
    mid = (lo + hi + 1) // 2
    if q * (f(i + mid) - f(i)) <= 10 ** 99 + mid * p:
        lo = mid
    else:
        hi = mid - 1
print(lo + i + 1)