AtCoder Beginner Contest 246 D

https://atcoder.jp/contests/abc246/tasks/abc246_d

パッと見、数学的な問題のようですが、そんなことは全然ありません。

f:id:inamori:20220406201211p:plain

(b, a) = (0, 5)から辿っていくだけです。計算量は O(N^{1/3})です。

# coding: utf-8
# 2-variable Function

from itertools import count


#################### library ####################

def read_int():
    return int(raw_input())

def int_root(n, e):
    r0 = int(n ** (1./e))
    if r0 ** e <= n:
        for r in count(r0 + 1):
            if r ** e > n:
                return r - 1
    else:
        for r in count(r0 - 1, -1):
            if r ** e <= n:
                return r


#################### process ####################

def read_input():
    N = read_int()
    return N

def F(N):
    min_X = N*2
    a = int_root(N, 3) + 1
    for b in count():
        while True:
            X = (a + b) * (a*a + b*b)
            print (a, b, X)
            if X < N:
                a += 1
                break
            elif X < min_X:
                min_X = X
            a -= 1
            if a < 0:
                break
        if a < b:
            break
    return min_X


#################### main ####################

N = read_input()
print F(N)