abc193のC問題 整数系の問題を解く
AtcoderのABC193に参加して解けたC問題のふりかえりです。
整数 N が与えられて、1 以上 N 以下の整数のうち、2 以上の整数 a,bを用いてと表せないものはいくつあるでしょうか?
読解力がない自分は短い問題の方が好きです。
atcoder.jp
まずNは最大でなので、全探索は無理。
aが例えば最小の2のとき、bが最小の2のとき、それぞれのaとbはいくつになるんだろうと考えつけば、
aとbの探索範囲が現実的になってきます。
bが2の時は、なので、aの範囲は
aが2の時は、なので、bの範囲は
aもbも整数なので、適宜値を切り捨てたり、切り上げたりします。
max_a = ceil(sqrt(N)) max_b = floor(log2(N))
あとはの値が重複して数えないようにして、Nからが成立した回数を引いてあげれば答えです。
from math import log2 from math import floor, ceil from math import sqrt N = int(input()) max_b = floor(log2(N)) max_a = ceil(sqrt(N)) ok_set = set() for b in range(2, max_b + 1): for a in range(2, max_a + 1): if a ** b <= N: ok_set.add(a**b) else: break count = len(ok_set) print(N - count)
最初に対数をとって、あれこれと不等式を数学的に解けないか考えて、無駄な時間を過ごしてしまったことは反省。。。
公式の解説は頭が良すぎる簡潔な表現で、コードも簡潔で劣等感を感じました。