记录编号	119861	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1481] 寻找素数项	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	C++	运行时间	0.863 s
提交时间	2014-09-14 17:22:02	内存使用	0.29 MiB

#include<cstdio>
using namespace std;
inline long long qe(long long a, int b, int c){
	long long s(1);
	while (b){
		if (b & 1) s = s * a % c;
		b >>= 1;
		a = a * a % c;
	}
	return s;
}
inline bool test(int x, int a){
	int d(x - 1);
	while (~d & 1) d >>= 1;
	long long t(qe(a, d, x));
	if (t == 1 || t == x - 1) return true;
	while (d != x - 1){
		d <<= 1;
		t = t * t % x;
		if (t == x - 1) return true;
	}
	return false;
}
inline bool miller_rabin(int x){
	if (x == 2 || x == 7 || x == 61) return true;
	if (x < 2 || ~x & 1) return false;
	if (test(x, 2) && test(x, 7) && test(x, 61)) return true;
	return false;
}
int main(){
	freopen("primechecker.in", "r", stdin);
	freopen("primechecker.out", "w", stdout);
	int i, a;
	scanf("%d", &a);
	for (i = 1; i < 100000; ++i){
		printf("%d", (int)miller_rabin(a));
		a = a + 1234567890 & 0x7fffffff;
	}
	printf("%d\n", (int)miller_rabin(a));
	return 0;
}