Home > Old Blog Posts > USACO 1.5.2 Prime Palindromes

USACO 1.5.2 Prime Palindromes


一亿的范围摆出来,朴素一个一个数枚举的算法就过不了了(主要是空间问题,时间也难撑)。

所以我们先枚举回文,再判断是否是素数。

枚举方法:分回文长度是奇数或偶数两种情况,枚举一半数,再复制另一半,如枚举到521,奇数复制为52125,偶数复制为521125。

进一步思考,除2外,所有的偶数都不可能是质数;除11外,所有偶数长度的回文都不可能是质数(用数学方法可以证明,详略)。

想zhuangbility的话,素数检验用miller-rabin吧..

代码:

/*
ID: dementr1
PROG: pprime
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
ifstream fin(“pprime.in”);
ofstream fout(“pprime.out”);
int A,B,ans[1000],num=0;
void init()
{
fin>>A>>B;
}
bool judge(int n)
{
unsigned k, p, q, t;
unsigned long long a;
for (q = 0, p = n-1; p % 2 == 0; p /= 2, ++q);
for (k = 1, t = p; t /= 2; k *= 2);
for (int times = 2; times; –times)
{
unsigned i = rand() % (n-2) + 2;
for (a = i % n, t = k; t /= 2; )
{
a = a * a % n;
if (t & p) a = a * i % n;
}
if (a == 1) continue;
for (i = q; i; –i)
{
unsigned long long b = a * a % n;
if (b == 1)
{
if (a == n-1) goto L1;
return false;
}
a = b;
}
if (a != 1) return false;
L1:;
}
return true;
}
void work()
{
int a,b,c,d,tmp;
ans[num++]=5;
ans[num++]=7;
ans[num++]=11;
for(a=1;a<=9;a+=2)
for(b=0;b<=9;b++)
{
tmp=a*101+b*10;
if(judge(tmp)) ans[num++]=tmp;
tmp=a*1001+b*110;
if(judge(tmp)) ans[num++]=tmp;
}
for(a=1;a<=9;a+=2)
for(b=0;b<=9;b++)
for(c=0;c<=9;c++)
{
tmp=a*10001+b*1010+c*100;
if(judge(tmp)) ans[num++]=tmp;
tmp=a*100001+b*10010+c*1100;
if(judge(tmp)) ans[num++]=tmp;
}
for(a=1;a<=9;a+=2)
for(b=0;b<=9;b++)
for(c=0;c<=9;c++)
for(d=0;d<=9;d++)
{
tmp=a*1000001+b*100010+c*10100+d*1000;
if(judge(tmp)) ans[num++]=tmp;
tmp=a*10000001+b*1000010+c*100100+d*11000;
if(judge(tmp)) ans[num++]=tmp;
}
}
void print()
{
int start=0,end=num-1,i;
while(ans[start]<A) start++;
while(ans[end]>B) end–;
for(i=start;i<=end;i++) fout<<ans[i]<<endl;
}
int main()
{
init();
work();
print();
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: