結果

問題 No.28 末尾最適化
コンテスト
ユーザー なお
提出日時 2014-09-30 00:07:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 288 ms / 5,000 ms
コード長 1,598 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 888 ms
コンパイル使用メモリ 71,092 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 06:40:54
合計ジャッジ時間 1,571 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#ifdef _MSC_VER
#include "_lib_msc.h"
#endif
#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))

const int INF = 1<<29;
const int MOD = 100000009;

// 素因数分解
vector<pair<int,int> > pdecomp(unsigned int n){
    vector<pair<int,int> > res;
    unsigned int e = 0; while(n % 2 == 0){ n /= 2, e++; }
    if(e) res.push_back(make_pair(2,e));
    for(unsigned int p = 3; p*p <= n; p += 2){
        unsigned int e = 0; while(n % p == 0){ n /= p, e++; }
        if(e) res.push_back(make_pair(p,e));
    }
    if(n != 1) res.push_back(make_pair(n,1));
    return res;
}

int solve(ll s, int n, int k, int b){
    vector<int> x;
    x.push_back((int)s);
    REP(i,n){
        s = 1+(s*s+s*12345)%MOD;
        x.push_back((int)s);
    }
    vector<pair<int,int> > d = pdecomp(b);

    int minv = INF;
    FOREACH(it, d){
        const int p = it->first, e = it->second;
        vector<int> y;
        FOREACH(jt, x){
            int n = *jt, c = 0;
            while(n % p == 0){
                c++, n /= p;
            }
            y.push_back(c);
        }
        sort(y.begin(), y.end());
        int sum = 0;
        REP(j,k) sum += y[j];
        minv = min(minv, sum/e);
    }

    return minv;
}

int main(){
    int N,s,n,k,b;
    cin >> N;

    REP(i,N){
        cin >> s >> n >> k >> b;
        cout << solve(s,n,k,b) << endl;
    }

    return 0;
}
0