結果

問題 No.28 末尾最適化
ユーザー yaoshimaxyaoshimax
提出日時 2015-02-15 01:11:55
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,826 bytes
コンパイル時間 742 ms
コンパイル使用メモリ 91,380 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-23 20:17:57
合計ジャッジ時間 1,407 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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};
  int n_prime=10;
  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