結果

問題 No.28 末尾最適化
ユーザー hotpepsihotpepsi
提出日時 2015-06-28 23:11:40
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 330 ms / 5,000 ms
コード長 878 bytes
コンパイル時間 576 ms
コンパイル使用メモリ 64,832 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-07-07 20:58:28
合計ジャッジ時間 1,965 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <sstream>
#include <numeric>

using namespace std;

typedef long long LL;

int main(int argc, char *argv[])
{
	string s;
	getline(cin, s);
	stringstream sa(s);
	int Q;
	sa >> Q;
	for (int i = 0; i < Q; ++i) {
		getline(cin, s);
		stringstream sb(s);
		LL x[10001] = {}, N, K, B, y[10001];
		sb >> x[0] >> N >> K >> B;
		for (int j = 1; j <= N; ++j) {
			x[j] = 1 + (x[j - 1] * (x[j - 1] + 12345)) % 100000009;
		}

		LL ans = 1 << 30;
		for (int p = 2; B > 1; ++p) {
			LL f = 0;
			while ((B % p) == 0) {
				++f;
				B /= p;
			}
			if (f > 0) {
				for (int j = 0; j <= N; ++j) {
					int cnt = 0;
					LL n = x[j];
					while ((n % p) == 0) {
						++cnt;
						n /= p;
					}
					y[j] = cnt;
				}
				sort(y, y + N + 1);
				ans = min(ans, accumulate(y, y + K, 0LL) / f);
			}
		}
		cout << ans << endl;
	}

	return 0;
}
0