結果
問題 | No.28 末尾最適化 |
ユーザー | 沙耶花 |
提出日時 | 2021-10-21 13:01:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 118 ms / 5,000 ms |
コード長 | 1,063 bytes |
コンパイル時間 | 4,530 ms |
コンパイル使用メモリ | 263,884 KB |
実行使用メモリ | 6,940 KB |
最終ジャッジ日時 | 2024-09-21 08:13:54 |
合計ジャッジ時間 | 4,942 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 118 ms
6,940 KB |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 100000001 int main(){ int Q; cin>>Q; rep(_,Q){ long long seed,N,K,B; cin>>seed>>N>>K>>B; vector<pair<int,int>> ps; for(int i=2;i<=B;i++){ if(B%i==0){ ps.emplace_back(i,0); while(B%i==0){ B/=i; ps.back().second++; } } } vector<long long> a(N+1); a[0] = seed; for(int i=1;i<=N;i++){ a[i] = a[i-1] * (a[i-1] + 12345); a[i] %= 100000009; a[i]++; } int ans = Inf; rep(i,ps.size()){ vector<int> cnt(35,0); rep(j,N+1){ int temp = a[j]; int c = 0; while(temp%ps[i].first==0){ temp /= ps[i].first; c++; } cnt[c]++; } int KK = K; int S = 0LL; rep(j,cnt.size()){ if(KK<=cnt[j]){ S += j * KK; break; } KK -= cnt[j]; S += cnt[j] * j; } ans = min(ans,S/ps[i].second); } cout<<ans<<endl; } return 0; }