結果

問題 No.28 末尾最適化
コンテスト
ユーザー yaoshimax
提出日時 2015-02-15 01:20:20
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 311 ms / 5,000 ms
コード長 1,829 bytes
コンパイル時間 775 ms
コンパイル使用メモリ 91,720 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-06-23 20:17:59
合計ジャッジ時間 1,466 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:24:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   24 |   scanf("%d",&Q);
      |   ~~~~~^~~~~~~~~
main.cpp:29:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   29 |     scanf("%d%d%d%d",&seed,&N,&K,&B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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