結果

問題 No.28 末尾最適化
コンテスト
ユーザー simezi_tan
提出日時 2015-07-22 22:03:42
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 251 ms / 5,000 ms
コード長 986 bytes
コンパイル時間 2,230 ms
コンパイル使用メモリ 163,568 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-08 12:04:36
合計ジャッジ時間 2,141 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int main(){
	int q; cin >> q;
	while(q--){
		int s, n, k, b, ans = inf;
		vi v;
		cin >> s >> n >> k >> b;
		v.pb(s);
		rep(i, n){
			s = 1 + ((ll)s * s + s * 12345ll) % ((int)1e8 + 9);
			v.pb(s);
		}
		
		for(int i = 2; i <= b; i++) if(b % i == 0){
			
			int c = 0;
			vi cnt;
			for(; b % i == 0; b /= i) c++;
			
			rep(l, n + 1){
				int k = 0;
				for(int j = v[l]; j % i == 0; j /= i) k++;
				cnt.pb(k);
			}
			sort(all(cnt));
			int x = 0;
			rep(l, k) x += cnt[l];
			ans = min(ans, x / c);
		}
		cout << ans << endl;
	}
	return 0;
}
0