結果

問題 No.28 末尾最適化
ユーザー yaoshimaxyaoshimax
提出日時 2015-02-15 01:20:20
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 306 ms / 5,000 ms
コード長 1,829 bytes
コンパイル時間 646 ms
コンパイル使用メモリ 91,540 KB
実行使用メモリ 4,376 KB
最終ジャッジ日時 2023-09-06 01:11:52
合計ジャッジ時間 1,360 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;
int main(){
  int Q;
  scanf("%d",&Q);
  int primes[]={2,3,5,7,11,13,17,19,23,29,31};
  int n_prime=11;
  for( int qi = 0 ; qi < Q; qi++ ){
    int seed,N,K,B;
    scanf("%d%d%d%d",&seed,&N,&K,&B);
    int ps[3];
    int pcnt[3];
    int psize=0;
    for( int pi = 0 ; pi < n_prime; pi++ ){
      int p = primes[pi];
      int cnt =0;
      while(B%p==0){
        cnt++;
        B/=p;
      }
      if(cnt>0){
        //cout << p << ", "<< cnt;
        ps[psize]=p;
        pcnt[psize]=cnt;
        psize++;
      }
    }
    priority_queue<int> pq[psize];
    for( int i = 0 ; i < N+1; i++ ){
      long long x = seed;
      //cout << seed;
      for( int j = 0 ; j < psize; j++ ){
        int p = ps[j];
        int cnt = 0;
        while( seed%p == 0 ){
          cnt++;
          seed/=p;
        }
        //cout <<" "<<cnt;
        if( pq[j].size() < K ){
          pq[j].push(cnt);
        }
        else if( pq[j].top() > cnt ){
          pq[j].pop();
          pq[j].push(cnt);
        }
      }
      //cout << endl;
      long long s= x*x;
      s%=100000009;
      s += x*12345;
      s%=100000009;
      seed=s+1;
    }
    int ans = INT_MAX;
    for( int pi = 0 ; pi < psize; pi++ ){
      int div = pcnt[pi];
      int sum = 0;
      for( int j = 0 ; j < K ; j++ ){
        sum += pq[pi].top();
        pq[pi].pop();
      }
      //cout << sum << "/ "<< div<<endl;
      ans = min(ans,sum/div);
    }
    printf("%d\n",ans);
  }
  return 0;
}
0