競技プログラミングにハマるプログラマのスレ 145

[0274 仕様書無しさん 2023/12/28(木) 02:01:11.89]

O(NlogK)が自明なのにO(N)がそんなに嬉しいのか？
線形篩を使えばx^K(1<x<N, K<N)はO(N)ではある
素数は愚直にO(logK)で求めると、素数の個数はO(N/logN)個なのでK<Nの仮定からO(N)
あとは 20^K = 2^K × 10^K とかやればよいため