A. Primes or Palindromes?
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://poj.org/problem?id=3261
Description
Rikhail Mubinchik believes that the current definition of prime numbers is obsolete as they are too complex and unpredictable. A palindromic number is another matter. It is aesthetically pleasing, and it has a number of remarkable properties. Help Rikhail to convince the scientific community in this!
Let us remind you that a number is called prime if it is integer larger than one, and is not divisible by any positive integer other than itself and one.
Rikhail calls a number a palindromic if it is integer, positive, and its decimal representation without leading zeros is a palindrome, i.e. reads the same from left to right and right to left.
One problem with prime numbers is that there are too many of them. Let‘s introduce the following notation: π(n) — the number of primes no larger than n, rub(n) — the number of palindromic numbers no larger than n. Rikhail wants to prove that there are a lot more primes than palindromic ones.
He asked you to solve the following problem: for a given value of the coefficient A find the maximum n, such that π(n) ≤ A·rub(n).
Input
, 
).Output
If such maximum number exists, then print it. Otherwise, print "Palindromic tree is better than splay tree" (without the quotes).
Sample Input
1 1
Sample Output
40
HINT
题意
给你p,q，A=p/q
π(n)表示1-n中素数的个数
rub(n)表示1-n中回文数的个数
求最大的n，满足π(n) ≤ A·rub(n).
题解：
CF测评姬很快，1e7直接上暴力就好了
代码：
//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 10050000 #define mod 10007 #define eps 1e-9 int Num; char CH[20]; //const int inf=0x7fffffff; //нчоч╢С const int inf=0x3f3f3f3f; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } //************************************************************************************** bool flag[maxn]; int primes[maxn], pi; int pa[maxn]; void GetPrime() { int i, j; pi = 0; memset(flag, false, sizeof(flag)); for (i = 2; i < maxn; i++) { primes[i]+=primes[i-1]; if (!flag[i]) { primes[i] ++ ; for (j = i; j < maxn; j += i) flag[j] = true; } } } int check_Pa(int x) { int X=x; int x2=0; while(X) { x2*=10; x2+=X%10; X/=10; } return x2==x?1:0; } void GetPa() { for(int i=1;i<maxn;i++) { pa[i]+=pa[i-1]; if(check_Pa(i)) pa[i]++; } } int main() { GetPrime(); GetPa(); double p,q; cin>>p>>q; double A=p/q; int ans=0; for(int i=1;i<maxn;i++) { if(A*pa[i]*1.0>=primes[i]*1.0) ans=i; } if(ans==0) cout<<"Palindromic tree is better than splay tree"<<endl; else cout<<ans<<endl; }
Codeforces Round #315 (Div. 1) A. Primes or Palindromes? 暴力
原文：http://www.cnblogs.com/qscqesze/p/4719862.html