結果
問題 | No.28 末尾最適化 |
ユーザー |
![]() |
提出日時 | 2014-11-01 23:54:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 270 ms / 5,000 ms |
コード長 | 972 bytes |
コンパイル時間 | 1,731 ms |
コンパイル使用メモリ | 161,936 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-30 16:10:05 |
合計ジャッジ時間 | 2,735 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:23:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 23 | scanf("%d",&Q); | ~~~~~^~~~~~~~~ main.cpp:25:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | scanf("%d%d%d%d",&seed,&N,&K,&B); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h>using namespace std;#define REP(i,a,b) for(i=a;i<b;i++)#define rep(i,n) REP(i,0,n)#define ll long long#define ull unsigned ll#define INF 1000000000int Q;int seed, N, K, B;int X[100000];int Y[100000];int p[20], pn[20], ps;int main(){int i, j, k;int res;scanf("%d",&Q);while(Q--){scanf("%d%d%d%d",&seed,&N,&K,&B);N++;X[0] = seed;REP(i,1,N) X[i] = 1 + (((ll)X[i-1]*X[i-1] + (ll)X[i-1]*12345) % 100000009);ps = 0;for(i=2;i<=B;i++){if(B%i==0){p[ps] = i;pn[ps] = 0;while(B%i==0) pn[ps]++, B/=i;ps++;}}res = INF;rep(k,ps){rep(i,N){Y[i] = 0;j = X[i];while(j%p[k]==0) j/=p[k], Y[i]++;}sort(Y, Y+N);j = 0;rep(i,K) j += Y[i];res = min(res, j/pn[k]);}printf("%d\n",res);}return 0;}