結果

問題 No.28 末尾最適化
ユーザー なおなお
提出日時 2014-09-30 00:07:36
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 244 ms / 5,000 ms
コード長 1,598 bytes
コンパイル時間 613 ms
コンパイル使用メモリ 71,384 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-09 15:02:14
合計ジャッジ時間 1,229 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#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