意外に手間取った。
https://yukicoder.me/problems/no/1666
問題
正整数aと2以上の整数bを用いてx=a^bの形で表現できるxを累乗数と呼ぶことにする。
小さい順からN番目の累乗数はいくつか。
解法
f(v) := v以下の累乗数の個数
とすると、f(v)は単調増加なのでf(v)≧Nである最小のvを求める二分探索問題に落とせる。
あとはf(v)を求めよう。
bは高々O(log v)通りしかありえないので、bを総当たりする。
ただし包除原理の要領で、
- bを素因数分解したとき、次数が2以上の素因数があるようなbは無視する。
- bを素因数分解したとき、素因数の数の偶奇によって、(floor(vのb乗根)-1)をf(v)に加減算する。
int T; ll K; ll num(ll v) { ll sum=1; for(int i=2;i<=60;i++) { int num=1; int x=i; for(int j=2;j<=i;j++) if(x%j==0) { num*=-1; if(x%(j*j)==0) num=0; while(x%j==0) x/=j; } if(num==0) continue; ll a=pow(v,1.0/i)+2; while(1) { __int128 b=1; int j; FOR(j,i) b*=(a-1); if(b>=v) a--; else break; } a--; if(num==-1) { sum+=a-1; } else { sum-=a-1; } } return sum; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>K; ll ret=1LL<<60; for(i=59;i>=0;i--) if(num(ret-(1LL<<i))>=K) ret-=1LL<<i; cout<<ret-1<<endl; } }
まとめ
シンプルな問題設定。