結果

問題 No.28 末尾最適化
コンテスト
ユーザー kyuridenamida
提出日時 2016-02-11 08:41:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 230 ms / 5,000 ms
コード長 1,005 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,411 ms
コンパイル使用メモリ 167,580 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-22 00:20:29
合計ジャッジ時間 2,143 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0 ; (i) < (int)(n) ; (i)++)
#define REP(i,a,b) for(int (i) = a ; (int)(i) <= (int)(b) ; (i)++)
#define all(n) (n).begin(),(n).end()
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int,int> Pii;
typedef vector<Pii> VPii;


void solve(vector<int> A,int K,int B){
	vector< pair<int,int> > p;
	REP(i,2,B){
		if( B % i == 0 ){
			int c = 0;
			while( B % i == 0 ) B /= i, c++;
			p.push_back({i,c});
		}
	}
	int r = 1e9;
	for( auto target : p ){
		vector<int> C;
		rep(i,A.size()){
			int t = A[i];
			int c = 0;
			while( t % target.first == 0 ) t /= target.first, c++;
			C.push_back(c);
		}
		sort(all(C));
		int tot = 0;
		rep(i,K) tot += C[i];
		r = min(r,tot / target.second );
	}
	cout << r << endl;
	
}
int main(){
	int Q;
	cin >> Q;
	rep(i,Q){
		int s,N,K,B;
		cin >> s >> N >> K >> B;
		Vi A(N+1);
		A[0] = s;
		REP(j,1,N) A[j] = 1 + (1ll * A[j-1] * A[j-1] + A[j-1] * 12345ll) % 100000009;
		solve(A,K,B);
	}
}
0