7K12 blog

猫でも分かるアルゴリズム解説

ABC106 B - 105

f:id:tkr987:20200611205741p:plain

https://atcoder.jp/contests/abc106/submissions/14176996

f:id:tkr987:20200611210915p:plain
約数の個数は素因数分解した因数の(指数+1)の積で得られる。

素因数分解の計算量は O(\sqrt N)なので、全探索しても全体計算量 O(N\sqrt N)でTLEしない。