codeforces 569 C Primes or Palindromes? (暴力)
先预处理出来比小于等于n的素数的个数和回文数的个数...
素数不筛竟然也可以过
然后暴力就好.
需要注意的是,比值并不单调,找最大的n,可能之前某个数开始不满足条件,之后又有满足条件的了.
我们可以倒着扫来找,第一个满足条件的就是最大的.
/*************************************************************************
> File Name: code/cf/#315/C.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月11日 星期二 00时54分13秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=2E6+5;
25int f[N],g[N];
26bool prime( int x)
27{
28 if (x==1) return false;
29 if (x<=3) return true;
30 for ( int i = 2 ; i*i<=x ; i ++)
31 {
32 if (x%i==0)
33 return false;
34 }
35 return true;
36}
37bool pal( int x)
38{
39 int a[100];
40 int len=0;
41 while(x)
42 {
43 len++;
44 a[len]=x;
45 x = x/ 10;
46 }
1 for ( int i = 1 ;i <= len/2 ; i++)
2 {
3 if (a[i]!=a[len+1-i])
4 return false;
5 }
6 return true;
7}
8int main()
9{
10 int cnt = 0;
11 memset(f,0,sizeof(f));
12 memset(g,0,sizeof(g));
13 for (int i = 1 ; i <= N-5 ; i ++)
14 {
15 if (prime(i))
16 {
17 cnt++;
1 // pri[cnt] = i;
2 }
3 f[i] = cnt;
4 }
5 int cnt2 = 0 ;
6 for ( int i =1 ; i <=N-5 ; i++)
7 {
8 if (pal(i))
9 {
10 cnt2++;
1 }
2 g[i] = cnt2;
3 }
4 // for ( int i =1; i <= N-5; i ++)
5 // {
6// cout<<"i:"<<i<<"f[i]:"<<f[i]<<" g[i]:"<<g[i]<<"f[i]/g[i]:"<<f[i]*1.0/g[i]*1.0<<" g[i]/f[i]"<<g[i]*1.0/f[i]<<endl;
7 // }
8 int p,q;
9 int i = 0;
10 scanf("%d %d",&q,&p);
11 double r = p*1.0/q;
12 for ( int i = N-5 ; i >= 1 ; i--)
13 {
14 if (r*f[i]<=g[i])
15 {
16 cout<<i<<endl;
17 break;
18 }
19 }
return 0;
}