问题 F: 超超的自闭意思

时间限制: 1 Sec 内存限制: 128 MB
提交: 80 解决: 10
[提交] [状态] [命题人:jsu_admin]

题目描述

质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
回文数定义为在正整数中，从左到右，从右到左读都相同的数字。（没有前导零的十进制）

现在 z(n) 表示不大于n的质数个数，h(n)表示不大于n的回文数个数。
给定两个数b, a。求最大n，满足b * z(n) ≤ a * h(n)。

输入

第一行包含一个整数T，表示有T组数据, T <= 10
每组数据包含两个整数b, a, 如题所述。
b,a < 10^4 , 1 / 42 <=b /a <= 42

输出

如果存在这样的n，则打印出来。如果不存在这样的n ，输出 “No”

样例输入 Copy

2
1 1
4 6

样例输出 Copy

40
16

我们可以估算出最大的 n，当 a=1，b=10000 的时候，打表出来我们发现只会到达 2*1e6，所以我们可以从 1-2*1e6 开始判断，判断到新的满足要求的 n 就更新，但是我们每次单独判断一个数是不是素数很费时间，会超时，所以我们用素筛打一个表节约时间，然后判断一个数是不是回文也是根据那个数的位数来的，所以不必担心，然后就是直接暴力判断

  1 #include<stdio.h>
  2 #include<vector>
  3 #include<cstring>
  4 #include<cmath>
  5 using namespace std;
  6 int cnt = 0;
  7 const int MAXN = 5010;
  8 int prime[MAXN];//第i个素数
  9 bool is_pri[MAXN+10];//is_pri[i]表示i是素数
 10 //返回n以内素数的个数
 11 int sieve(int n){
 12 int p=0;
 13 for(int i=0;i<=n;i++)is_pri[i]=true;
 14 is_pri[0]=is_pri[1]=false;
 15 for(int i=2;i<=n;i++){
 16     if(is_pri[i]){
 17 prime[++p]=i;
 18         for(int j=2*i;j<=n;j+=i)is_pri[j]=false;
 19 }
 20 }
 21 return p;
 22 }
 23 //回文数 
 24 int palindrome(int a,int x)
 25 {
 26     int t;
 27     do
 28     {
 29         t=x%10;
 30         a=a*10+t;
 31         x=x/10;
 32     }
 33     while(x>0);
 34     return a;
 35 }
 36  
 37 int huiwen(int n)
 38 {
 39     int a,x,c,i;
 40   //  while(scanf("%d",&n)&&n!=0)
 41   //  {
 42         c=0;
 43         for(i=1; i<=n; i++)
 44         {
 45             a=0;
 46             x=i;
 47             a=palindrome(a,x);
 48             if(a==i)  c++;
 49         }
 50       //  printf("%d
",c);
 51 //    }
 52    return c;
 53 }
 54 
 55 bool isPrime(int num)
 56 {
 57     if(num == 2)
 58         return true;
 59     int tmp = sqrt(num);
 60     for(int i=2;i<=tmp;i++)
 61     {
 62         if(num%i == 0)
 63         {
 64             return false;
 65         }
 66     }
 67     return true;
 68 }
 69 bool isHuiwen(int x)
 70 {
 71     int newed,t,n;
 72   //  while(scanf("%d",&x)!=EOF)
 73     //{
 74         newed=0;
 75         n=x;
 76         do
 77         {
 78             newed=newed*10+x%10;
 79             x/=10;
 80         }while(x>0);
 81         if(n==newed)
 82             return true;
 83         else
 84           return false;
 85   //  }
 86 }
 87 int dp[3000020];
 88 int dp2[3000020];
 89 
 90 void dabiao(){
 91     dp[0] = 0;
 92     dp[1] = -1;
 93     dp2[0] = 0;
 94     for(int i = 1;i<2*1e6+100;i++)
 95     {
 96         dp[i] += dp[i-1]+isPrime(i);
 97         dp2[i] += dp2[i-1]+isHuiwen(i);
 98     }
 99 }
100 int main()
101 {
102     int t;
103     int b , a;
104     dabiao();
105     scanf("%d",&t);
106     
107     for(int i = 0 ;i < t;i++)
108     {
109     //    cnt = 0;
110         int sum = 0;
111         scanf("%d%d",&b,&a);
112         for(int j = 1;j<2*1e6+100;j++){
113         ///    vector<int> prime = Prime(j);
114         //     cnt = prime.size();
115             if(a*dp[j]<=b*dp2[j])//b*Prime(n)<=a*huiwen(n)
116             sum = j;
117         
118         }
119             if(sum)
120             printf("%d
",sum);
121             else
122             printf("No");
123     }
124 }

View Code