トリッキー問題コンテスト : C - 階乗と素因数

A,Bは境界条件を回避するある意味面倒な問題だが、こちらは真っ当に面白い問題だった。
http://tricky.contest.atcoder.jp/tasks/tricky_3

問題

自然数Nと素数pについて、F(N,p)はN!の素因数としてpが何回登場するかを示す。
p,xが与えられたとき、N - F(N,p) = xとなる最小のNを求めよ。

解法

Nを1つずつ大きくしていった場合、Nがpで割り切れるタイミングでF(N,p)が増加する。
p>=3の場合、F(N,p)の増加ペースはNの増加ペースより小さいため、N-F(N,p)は段々大きくなっていずれxに到達する。
Nがさほど大きくなる前にxに到達するので、総当たりで題意を満たすNを検証すればよい。

問題はp=2の時で、この場合なかなかN - F(N,p)が大きくならない。
ただ、小さ目のxで試すとxに対しN==2^x-1の時題意を満たすことがわかる。

void solve() {
	int f,i,j,k,l,x,y,loop;
	int T;
	cin>>T;
	FOR(loop,T) {
		ll X,P;
		ll mp[32];
		scanf("%lld%lld",&P,&X);
		
		if(X==0) {
			_P("0\n");
			continue;
		}
		if(P==2) {
			_P("%lld\n",(1LL<<X)-1);
			continue;
		}
		
		
		mp[1]=P;
		for(i=1;i<30;i++) mp[i+1]=mp[i]*P;
		
		ll num=0;
		int mo=0;
		int inc=0;
		for(ll cur=1;cur<1LL<<30;cur++) {
			mo++;
			if(mo==P) {
				for(i=1;i<=30;i++) {
					if(mp[i]>cur) break;
					if((cur % mp[i])==0) num++;
				}
				mo=0;
			}
			if(cur-num==X) {
				_P("%lld\n",cur);
				break;
			}
		}
	}
}

まとめ

これはなかなか面白い問題で良かった。
1回で正解できたしね。