ABC361Fを解いた

筆者はレート600前後の茶色コーダ

この前開催されたABC361で解けなかった以下の問題を解いていく

実装コード

2番目の解説の方針に従い、$b=2$は計算で求め$b \ge 3$以降を全探索的な感じに調べる
$b = [3,60)$ の区間で $a^b$ の値を計算し、$N$より大きくなったら$b$を1増やして最初から、
求めた$a^b$が何らかの数字$c$で$c^2$と表記できない場合は数えるようにして。
区間内の計算が終わったら計算で求めた$b=2$の個数と$b = [3,60)$で探索した結果を合算すればOK

$c^2$で表現できるか確かめる方法は平方根の小数点以下切り捨てで計算した整数値の2乗が元の値になるかで調べるみたい。
その時の平方根は解説の実装ではニュートン法?を使っているっぽい。

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args, end="\n"): print(*args,end=end, file=sys.stderr)

def sqrt_floor(x):
    l = 0
    r = 2000000000
    while l <= r:
        t = (l + r) // 2
        if t * t > x:
            r = t - 1
        else:
            l = t + 1
    return r

def main():
    N = rI()
    S = set()
    for i in range(3,60):
        for j in range(2,N):
            k = pow(j,i)
            if k > N:
                break
            x = sqrt_floor(k)
            if x**2 != k:
                S |= {k}
    print(len(S)+sqrt_floor(N))
if __name__ == '__main__':
    main()

まとめ

ABC361Fを解いた。
平方根を用いた探索と、ニュートン法を使用した平方根の計算アルゴリズムを実装した

感想

今回解いた問題は求める内容こそ単純だが、解法は数学の知識が必要で、簡単に解けそうで難しい問題だった。
このような問題を解けるようして、ABCの記録を伸ばせるようになりたい。