#1179520 (C(gnu17)) No.8030 ミラー・ラビン素数判定法のテスト

• 問題: No.8030 ミラー・ラビン素数判定法のテスト
• ユーザー: aqualength
• 提出日時: 2026-08-27 22:29:29
• 言語: C(gnu17) (gcc 15.3.0)
• 結果: WA
• 実行時間: -
• コード長: 5,270 bytes
• コンパイル時間: 199 ms
• コンパイル使用メモリ: 39,168 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-27 22:29:34
• 合計ジャッジ時間: 1,521 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
other	AC * 3 WA * 7

ソースコード

#include<unistd.h>
#define BSIZE 1000000000

//k … nを2x5進法で表したときの桁数(ex: n=1024 then k=1000)
#define decimals(n,k) do{k=1;if((n)/(k)>=100000) (k)*=100000;if((n)/(k)>=10000) (k)*=10000;if((n)/(k)>=1000) (k)*=1000;if((n)/(k)>=100) (k)*=100;if((n)/(k)>=10) (k)*=10;}while(0)

char readbuf[BSIZE+1],writebuf[BSIZE+1];
int _read=0,_write=0;



/**
 *@brief n^m mod pを求める
 *@details モンゴメリ演算を使わない ~手抜き~ シンプルな繰り返し二乗法で計算する。
 *@note 計算量はΘ(log m)
 *@param n 底
 *@param m 指数
 *@param p 法
 *@return n^m mod pを返す
 */
unsigned modPow(unsigned n,unsigned m,unsigned p){
	unsigned ans=1;
	while(m){
		if((m&1)!=0){ //mの最下位ビットが1なら
			ans=(unsigned long long)ans*n%p;
		}
		m/=2;
		n=(unsigned long long)n*n%p;
	}
	return ans;
}

/**
 *@details ミラーラビンの1ステップ,2工程目@n
 * a^dに対して、二乗をs回繰り返し、どこかで-1が出れば素数の可能性がある
 *@note 計算量はΘ(s)@n
 *s<=log(n)なので、Θ(logn)
 *@param [in] n 素数判定したい3以上の奇数n
 *@param [in] ad 1工程目で求めた数a^d
 *@param [in] s n-1を素因数分解した際の2の数
 *retval -1 nが素数の可能性がある
 *retval 0 nが確実に合成数
 */
int millerStepSecond32(unsigned n,unsigned ad,unsigned s){
	int i=0;
	while(i<s&&ad!=n-1){ //s回二乗を繰り返し、-1が現れないか確認する
		ad=(unsigned long long)ad*ad%n;
		i++;
	}
	if(n-1==ad){ //2^{{2^r}d}=-1となるrが存在した
		return -1; //素数の可能性がある
	}else{ //全てのrで2^{{2^r}d}!=-1
		return 0; //確実に合成数
	}
}

/**
 *@details ミラーラビンの1ステップ,1工程目@n
 * a^d=1なら、素数の可能性がある。そうでないなら、2工程目を行う
 *@note 1工程目のみの計算量は繰り返し二乗法のΘ(logd) \n
 * d<=(n-1)/2なので、最悪計算量Θ(logn)
 *@param [in] n 素数判定したい3以上の奇数n
 *@param [in] a 素数の証人(一般のミラー・ラビンの場合ランダムな数)
 *@param [in] s n-1を素因数分解した際の2の数
 *@param [in] d n-1を素因数分解した際の2以外の素因数の積
 *retval -1 nが素数の可能性がある
 *retval 0 nが確実に合成数
 */
int millerStep32(unsigned n,unsigned a,unsigned s,unsigned d){
	unsigned ad=modPow(a,d,n);
	if(ad!=1){ //a^dが1でないなら、2工程目を行う
		return millerStepSecond32(n,ad,s);
	}else{ //a^dが1
		return -1; //素数の可能性がある
	}
}

/**
 *@details n-1を2^s*dの形にする
 *@param [in] n 整数n
 *@param [out] s n-1を素因数分解した際の2の数
 *@param [out] d n-1を素因数分解した際の2以外の素因数の積
 */
void millerSplit32(unsigned n,unsigned *s,unsigned *d){
	*d=n-1;
	*s=0;
	while(0==(*d&1)){ //dが偶数の間、dを2で割り続ける
		*d/=2;
		(*s)++;
	}
}

/**
 *@details 32ビットで3以上の奇数に対する 決定的ミラー・ラビン @n
 *証人2,7,61でミラー・ラビンの1ステップを実行する
 *@note 計算量はn-1=2^s*dとすると、1工程目でΘ(logd),2工程目でΘ(s)@n
 *logd<=logn,s<=lognなので、証人1つにつきΘ(logn)@n
 *32ビットの場合、証人3つで確実に素数判定できるため、全体でΘ(logn)
 *param [in] n 素数判定をしたい3以上の奇数n
 *retval -1 nが素数
 *retval 0 nが素数でない
 */
int isPrimeOdds32(unsigned n){
	unsigned s,d;
	unsigned alist[]={2,7,61};
	int ans=-1;
	millerSplit32(n,&s,&d); //n-1を2^s*dに分離
	for(int i=0;i<3&&alist[i]<n;i++){ //最大3つの証人で素数判定
		ans&=millerStep32(n,alist[i],s,d); //いずれの証人でも合成数判定が出ていないなら、確実に素数
	}
	return ans;
}

/**
 *@brief 32ビット 決定的ミラー・ラビン
 *@note 計算量:nの桁数をkとしたとき、Θ(k) @n
 *ただし、四則演算はΘ(1)で完了するものとする
 *param [in] n 素数判定をしたい非負整数n
 *retval -1 nが素数
 *retval 0 nが素数でない
 */
int isPrime32(unsigned n){
	//あくまでラッパーに徹し、本格的な素数判定はisPrimeOdds32()に任せる
	if(n<=1){ //0,1は素数でない
		return 0;
	}else if(2==n){ //2は素数
		return -1;
	}else if(0==(n&1)){ //偶数は素数になり得ない
		return 0;
	}else{  //3以上の奇数
		return isPrimeOdds32(n); //ミラーラビン法
	}
}
// 非負整数を入力するサブルーチン
unsigned inputu(){
	unsigned ans=0;
	while(readbuf[_read]<=32) _read++;
	do{
		ans*=10;
		ans+=(readbuf[_read]-'0');
		_read++;
	}while(readbuf[_read]>32);
	return ans;
}

// 非負整数を出力するサブルーチン(n…出力する数,br…区切り文字)
void outputu(unsigned n,char br){
	register unsigned tmp=n,k=1,dif;
	decimals(tmp,k);
	do{
		dif=tmp/k;
		writebuf[_write++]=dif+'0';
		tmp-=(dif*k);k/=10;
	}while(k);
	br&&(writebuf[_write++]=br);
}

int main(int argc,char *argv[]){
	read(STDIN_FILENO,readbuf,BSIZE); //入力を一括読み込み
	int n;
	n=inputu();
	for(int i=0;i<n;i++){
		unsigned x=inputu();
		outputu(x,32);
		outputu(isPrime32(x)!=0,10);
	}
	write(STDOUT_FILENO,writebuf,_write); //一括で出力
	return 0;
}