結果

問題 No.28 末尾最適化
コンテスト
ユーザー pessimist
提出日時 2026-01-18 21:42:05
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 365 ms / 5,000 ms
コード長 1,431 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,585 ms
コンパイル使用メモリ 362,024 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-18 21:42:12
合計ジャッジ時間 5,826 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
constexpr ll MOD=1e8+9;
vector<vector<pair<int,int>>> fac;
void init(){
    fac.resize(37,vector<pair<int,int>>());
    for(int i=2;i<=36;++i){
        int p=2;
        vector<pair<int,int>> ps;
        auto num=i;
        while(p*p<=num){
            int cnt=0;
            while(num%p==0){
                ++cnt;
                num/=p;
            }
            if(cnt)ps.emplace_back(p,cnt);
            p+=1;
        }
        if(num!=1)ps.emplace_back(num,1);
        fac[i]=ps;
    }
}
void solve(){
    ll seed,T;
    ll N,K;
    cin>>seed>>N>>K>>T;
    vector<ll> X(1,seed);
    ll now=seed;
    for(int j=0;j<N;++j){
        now=1+(now*(now+12345)%MOD);
        X.emplace_back(now);
    }

    ll ans=MOD;
    for(auto&[p,cnt]:fac[T]){
        vector<int> cnts;
        for(const auto&x:X){
            auto num=x;
            int c=0;
            while(num%p==0){
                num/=p;
                ++c;
            }
            cnts.emplace_back(c);
        }
        ranges::sort(cnts);
        ll tans=accumulate(begin(cnts),begin(cnts)+K,0LL)/cnt;
        ans=min(ans,tans);
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    init();
    int T=1; cin>>T;
    while(T--)solve();
    return 0;
}
0