結果

問題 No.28 末尾最適化
ユーザー akakimidoriakakimidori
提出日時 2015-07-27 00:04:07
言語 C90
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 746 bytes
コンパイル時間 129 ms
コンパイル使用メモリ 25,580 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-22 23:46:14
合計ジャッジ時間 837 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>

#define M 1000

typedef long long int ln;

int comp(const void *c1,const void *c2){
	int t1=*(int *)c1;
	int t2=*(int *)c2;
	return t1-t2;
}

int main(void){

	int Q;
	scanf("%d",&Q);

	int seed[M];
	int N[M];
	int K[M];
	int B[M];
	int i;
	for(i=0;i<Q;i++){
		scanf("%d%d%d%d",&seed[i],&N[i],&K[i],&B[i]);
	}

	ln X[10001];

	for(i=0;i<Q;i++){
		X[0]=seed[i];
		int j;
		for(j=1;j<=N[i];j++){
			X[j]=1+(X[j-1]*X[j-1]+X[j-1]*12345)%100000009;
		}
		int count[10001];
		for(j=0;j<=N[i];j++){
			count[j]=0;
			while(X[j]%B[i]==0){
				count[j]++;
				X[j]/=B[i];
			}
		}
		qsort(count,N[i]+1,sizeof(int),comp);
		int res=0;
		for(j=0;j<K[i];j++){
			res+=count[j];
		}
		printf("%d\n",res);
	}
	return 0;
}
0