1217: VIJOS-P1042

时间限制: 0 Sec  

内存限制: 128 MB

提交: 78  

解决: 29

[ ][ ][ ]

题目描述

        有一天，雄霸传授本人风神腿法第一式：捕风捉影..............的步法（弟子一：堂主，你大喘气呀。风：你给我闭嘴。）捕风捉影的关键是换气（换不好就会大喘气...）。         使用捕风捉影这一招时并不是每一步都喘气，而是在特定的步数喘气。一般来说功力越高，喘气越稀疏。喘气的步数符合特定规律：第一要是SUSHU（弟子二：哇塞！堂主，你还会鸟语，我好好崇拜你呦！可是SUSHU是什么意思呢？风：笨蛋，那是汉语拼音！）第二要是一个回文数，回文数就是正反念一样的数，如：123321，121，5211314（弟子三：堂主，最后一个好象不是...风：废话，当然不是了，我是考察一下你们的纠错能力！）现在给出两个数M，N(5< =M< N< =100,000,000)，你要算出M，N之间需要换气的都有哪几步。（包括M，N）。算出来的可以提升为本堂一级弟子，月薪（1000000000000000000000000000000000000000000  MOD  10  ）元。

输入

两个整数M，N。用空格隔开。

输出

在M，N之间的换气点，每个一行。

样例输入

100 500

样例输出

101131151181191313353373383

#include
    
     #include
     
      int prime[4000];int psize;int from, to;void getPrime(){	memset(prime, 0, sizeof(prime));	psize = 0;	int i,j;	bool a[10000];	memset(a, -1, sizeof(a));	for (i = 2; i < 10000; i++){		if (!a[i])continue;		prime[psize++] = i;		for (j = i + i; j < 10000; j+=i)a[j] = false;	}}bool isPrime(int n){	int i;	for (i = 0;prime[i]*prime[i]<=n; i++)if (n%prime[i] == 0)return false;	return true;}void one(){	if (from>7)return;	if (from == 5)printf("5\n");	printf("7\n");}void three(){	if (from > 999)return;	int i, j,k;	int a[4] = { 1, 3, 7, 9 };	for (i = 0; i < 4;i++)	for (j = 0; j < 10; j++){		k = a[i] * 100 + j * 10 + a[i];		if ( k< from)continue;		if (k>to)return;		if (isPrime(k))printf("%d%d%d\n", a[i], j,a[ i]);	}}void five(){	if (from>99999)return;	int a[4] = { 1, 3, 7, 9 };	int i, j, k, l;	for (i = 0; i < 4;i++)	for (j = 0; j < 10;j++)	for (k = 0; k < 10; k++){		l = a[i] * 10000 + j * 1000 + k * 100 + j * 10 + a[i];		if (l
      
       to)return;		if (isPrime(l))printf("%d%d%d%d%d\n", a[i], j, k, j, a[i] );	}}void seven(){	if (from>9999999)return;	int a[4] = { 1, 3, 7, 9 };	int i, j, k, l,m;	for (i = 0; i < 4; i++)	for (j = 0; j < 10; j++)	for (k = 0; k < 10; k++)	for(m=0;m<10;m++){		l = a[i] * 1000000 + j * 100000 + k * 10000 + m * 1000 +k*100+j*10+ a[i];		if (l
       
        to)return;		if (isPrime(l))printf("%d%d%d%d%d%d%d\n", a[i], j, k,m,k, j, a[i]);	}}int main(){	getPrime();	prime[psize++]=10001;	scanf("%d%d", &from, &to);	one();	if (11 >= from && 11 <= to)printf("11\n");	three(); five(); seven();	return 0;}
       
      
     
    

上面这个5ms

再慢一点的算法:6311ms

#include
    
     #include
     
      #include
      
       int prime[4000];int psize;int from, to;void getPrime(){	memset(prime, 0, sizeof(prime));	psize = 0;	int i,j;	bool a[10000];	memset(a, -1, sizeof(a));	for (i = 2; i < 10000; i++){		if (!a[i])continue;		prime[psize++] = i;		for (j = i + i; j < 10000; j+=i)a[j] = false;	}}bool isPrime(int n){	int i;	for (i = 0;prime[i]*prime[i]<=n; i++)if (n%prime[i] == 0)return false;	return true;}bool isHuiwen(int n,int wei){	if (wei == 0||wei==1)return true;	int i;	if (n /(int) pow((double)10, wei-1) == n % 10){		n %= (int)pow((double)10, wei-1);		n /= 10;		if (isHuiwen(n, wei - 2))return true;	}	return false;}int main(){	getPrime();	prime[psize++]=10001;	scanf("%d%d", &from, &to);	if (from == 5)printf("5\n");	if (from <= 7 && to >= 7)printf("7\n");	if (11 >= from && 11 <= to)printf("11\n");	if (from < 100)from = 101;	for (; from <= to; from++){		int wei = log10((double)from)+1;		if (wei % 2 == 0){			from = pow((double)10, wei);			wei++;			if (from>to)break;		}		if (isPrime(from) && isHuiwen(from,wei))			printf("%d\n", from);	}	return 0;}
      
     
    

最慢42805ms

#include
    
     #include
     
      #include
      
       int prime[4000];int psize;int from, to;void getPrime(){	memset(prime, 0, sizeof(prime));	psize = 0;	int i,j;	bool a[10000];	memset(a, -1, sizeof(a));	for (i = 2; i < 10000; i++){		if (!a[i])continue;		prime[psize++] = i;		for (j = i + i; j < 10000; j+=i)a[j] = false;	}}bool isPrime(int n){	int i;	for (i = 0;prime[i]*prime[i]<=n; i++)if (n%prime[i] == 0)return false;	return true;}bool isHuiwen(int n,int wei){	if (wei == 0||wei==1)return true;	int i;	if (n /(int) pow((double)10, wei-1) == n % 10){		n %= (int)pow((double)10, wei-1);		n /= 10;		if (isHuiwen(n, wei - 2))return true;	}	return false;}int main(){	getPrime();	prime[psize++]=10001;	scanf("%d%d", &from, &to);	if (from == 5)printf("5\n");	if (from <= 7 && to >= 7)printf("7\n");	if (11 >= from && 11 <= to)printf("11\n");	if (from < 100)from = 101;	for (; from <= to; from++){		if (isPrime(from) && isHuiwen(from,log10((double)from)+1))			printf("%d\n", from);	}	return 0;}