记录编号	199539	评测结果	AAAAAAAAA
题目名称	[USACO 1.5] 回文质数	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2015-10-26 21:44:28	内存使用	0.29 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long L;

int a, b; 
int t[5] = {2,3,5,7,11}, A[5] = {2,3,7,61,24251};

int Create(int x, int mid)
{
	int res = x*10+mid;
	while(x) res = res*10+x%10, x /= 10;
	return res;
}

int gcd(int x, int y) {return y ? gcd(y, x%y) : x;}

L pow(L x, int y, L mod)
{
	if(y == 0) return 1;
	if(y == 1) return x;
	L t = pow(x, y>>1, mod);
	if(y&1) return (t*x%mod)*t%mod;
	return t*t%mod;
}

bool Prime(int x)
{
	int s = 0, r, mod = x--, i, j;
	while(!(x&1)) s++, x>>=1;
	r = x;
	
	for(i = 0; i < 5; i++)
	{
		if(pow((L)A[i], r, (L)mod) == 1) continue;
		L res = pow((L)A[i], r, (L)mod);
		for(j = 0; j < s; j++)
		{
			if(res == mod-1) break;
			res = res*res%mod;
		}
		if(j == s) return 0;
	}
	return 1;
}

void Initialize()
{
	freopen("pprime.in", "r", stdin);
	freopen("pprime.out", "w", stdout);
	scanf("%d %d", &a, &b);
	for(int i = 0; i < 5; i++)
		if(a <= t[i]) printf("%d\n", t[i]);
}

void Create_num(int len, int ed, int x)
{
	if(len == ed)
	{
		for(int i = 0; i <= 9; i++)
		{
			int num = Create(x, i);
			if(a <= num && num <= b && Prime(num)) printf("%d\n", num);
		}
		return ;
	}
	
	if(ed) for(int i = 0; i <= 9; i++) Create_num(len, ed+1, x*10+i);
	else for(int i = 1; i <= 9; i+=2) if(i != 5) Create_num(len, ed+1, x*10+i);
}

int main()
{
	Initialize();	
	if(a <= 999 && b >= 100) Create_num(1, 0, 0);
	if(a <= 99999 && b >= 10000) Create_num(2, 0, 0);
	if(a <= 9999999 && b >= 1000000) Create_num(3, 0, 0);
	return 0;
}