yukicoder : No.28 末尾最適化

これは★３でもよさそうだなぁ。
http://yukicoder.me/problems/9

問題

• 
• 

で定義される整数列Xを考える。

X[0..N]のうちK要素を取って掛け合わせた数をTとする。
TをB進数表記したとき、末尾の0は最小何個つくか。

解法

Bがと素因数分解されたとする。
次に、X[0]～X[N]を実際に求め、それぞれを素因数分解した場合にBを構成する素因数Piの何乗を持つか調べよう。
X[i]は完全に素因数分解する必要はなく、Piでだけ割ってみればよい。

各Piについて、X[0]～X[N]をPiの累乗数の小さい順にソートし、先頭K個の累乗数の和をQiで割ると、0何個分Piがあるかわかる。
この値をPiごとに計算して最小値を求めると良い。

int Q;
ll S,N,K,B;
int num[3][10003];
ll mo=100000009;

map<ll,int> enumdiv(ll n) {
	map<ll,int> V;
	for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>S>>N>>K>>B;
		N++;
		map<ll,int> D=enumdiv(B);
		vector<int> V;
		ITR(it,D) V.push_back(it->first);
		
		ZERO(num);
		FOR(i,N) {
			FOR(j,V.size()) {
				ll t=S;
				while(t%V[j]==0) num[j][i]++, t/=V[j];
			}
			S = 1+(S*S+S*12345)%mo;
		}
		int mi=1000000000;
		FOR(j,V.size()) {
			sort(num[j],num[j]+N);
			x=0;
			FOR(i,K) x+=num[j][i];
			mi=min(mi,x/D[V[j]]);
		}
		cout<<mi<<endl;
	}
}

まとめ

完全に素因数分解するとTLEしてアウトで、Piだけ割ればいいと気づけるかという問題かな。
最近の★４に比べるとだいぶラク。