結果

問題 No.28 末尾最適化
ユーザー btkbtk
提出日時 2015-05-07 19:38:39
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 472 ms / 5,000 ms
コード長 1,657 bytes
コンパイル時間 701 ms
コンパイル使用メモリ 71,844 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 19:56:03
合計ジャッジ時間 1,510 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 472 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;
#define LL long long
const LL mod = 100000009;
typedef pair<int, LL> P;
int main(void){
	LL X[20000];
	vector<vector<LL> >POW(40);
	vector<list<P> > fact(40);
	int work[40];//素因数分解の作業用配列
	//POW[i][K]=i^k<=MODを満たすi,kについてあらかじめ求めておく
	for (int i = 2; i < 37; i++){
		LL num = 1;
		POW.reserve(40);
		while (num < mod){
			POW[i].push_back(num);
			num *= i;
		}
		POW[i].push_back(num*i);
		work[i] = i;
	}
	//[2,36]について素因数分解
	for (int i = 2; i < 37; i++){
		if (work[i] != 1){
			int p = work[i];
			for (int j = p; j < 37; j+=p){
				P pf = make_pair(p, 0ll);
				while (work[j] % p == 0)pf.second++,work[j]/=p;
				fact[j].push_back(pf);
			}
		}
	}
	int Q;
	cin >> Q;
	while (Q--){
		int N, K, B;
		LL res = mod;
		cin >> X[0] >> N >> K >> B;
		N++;
		for (int i = 1; i < N; i++){
			X[i] = ((X[i - 1] * (X[i - 1] + 12345)) % mod)+1;
		}
		//Bの素因数pについて,Tに含まれるp^kの最小のkを求める
		for (auto& pf : fact[B]){
			int cnt[40] = { 0 };
			int sum = 0;
			int k = K;
			//あらかじめ求めておいたべき乗に対する二分探索で一応loglog(10^8)まで落とす
			for (int i = 0; i < N; i++){
				int H = (int)POW[pf.first].size() - 1;
				int L = 0;
				while (H - L > 1){
					int M = (H + L) / 2;
					if (X[i] % POW[pf.first][M])H = M;
					else L = M;
				}
				cnt[L]++;
			}
			for (int i = 0; i < 40; i++){
				sum += min(k, cnt[i])*i;
				k -= min(k, cnt[i]);
			}
			res = min(res, sum / pf.second);
		}


		cout << res << endl;
	}
	
}
0