kmjp's blog

競技プログラミング参加記です

yukicoder : No.1666 累乗数

意外に手間取った。
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;
	}
}

まとめ

シンプルな問題設定。