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;
}