結果
問題 | No.28 末尾最適化 |
ユーザー | tottoripaper |
提出日時 | 2014-11-16 23:02:34 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 354 ms / 5,000 ms |
コード長 | 1,520 bytes |
コンパイル時間 | 1,038 ms |
コンパイル使用メモリ | 73,388 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-08-30 07:25:34 |
合計ジャッジ時間 | 1,413 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 354 ms
4,376 KB |
ソースコード
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> typedef long long ll; typedef std::pair<int,int> P; const ll MOD = 100000009ll; int main(){ int Q; scanf("%d", &Q); for(int _=0;_<Q;_++){ ll seed, B; int N, K; scanf("%lld %d %d %lld", &seed, &N, &K, &B); std::vector<ll> v(N+1); v[0] = seed; for(int i=1;i<=N;i++){ v[i] = 1 + (v[i-1]*v[i-1]%MOD + v[i-1]*12345%MOD) % MOD; } std::vector<P> fs; for(int i=2;i*i<=B;i++){ if(B % i == 0){ int t = 0; while(B % i == 0){t += 1; B /= i;} fs.push_back(std::make_pair(i, t)); } } if(B > 1){fs.push_back(std::make_pair(B, 1));} // for(auto f : fs){ // printf("%d %d\n", f.first, f.second); // } std::vector<int> v2(N+1); int res = 1001001001; for(auto f : fs){ int p = f.first, q = f.second; for(int i=0;i<N+1;i++){ ll x = v[i]; int t = 0; while(x % p == 0){t += 1; x /= p;} v2[i] = t; } std::sort(v2.begin(), v2.end()); int sum = 0; for(int i=0;i<K;i++){ sum += v2[i]; } res = std::min(res, sum/q); } printf("%d\n", res); } }