问题 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 就更新，但是 我们每次单独判断一个数是不是素数很费时间，会超时，所以我们用素筛打一个表节 约时间，然后判断一个数是不是回文也是根据那个数的位数来的，所以不必担心，然 后就是直接暴力判断

#include
#include
#include
#include
using namespace std;
int cnt = ;
const int MAXN = ;
int prime[MAXN];//第i个素数
bool is_pri[MAXN+];//is_pri[i]表示i是素数
//返回n以内素数的个数
int sieve(int n){
int p=;
for(int i=;i<=n;i++)is_pri[i]=true; is_pri[]=is_pri[]=false; for(int i=;i<=n;i++){ if(is_pri[i]){ prime[++p]=i; for(int j=*i;j<=n;j+=i)is_pri[j]=false; } } return p; } //回文数 int palindrome(int a,int x) { int t; do { t=x%; a=a*+t; x=x/; } while(x>);
return a;
}

int huiwen(int n)
{
int a,x,c,i;
// while(scanf("%d",&n)&&n!=0)
// {
c=;
for(i=; i<=n; i++)
{
a=;
x=i;
a=palindrome(a,x);
if(a==i) c++;
}
// printf("%d\n",c);
// }
return c;
}

bool isPrime(int num)
{
if(num == )
return true;
int tmp = sqrt(num);
for(int i=;i<=tmp;i++) { if(num%i == ) { return false; } } return true; } bool isHuiwen(int x) { int newed,t,n; // while(scanf("%d",&x)!=EOF) //{ newed=; n=x; do { newed=newed*+x%; x/=; }while(x>);
if(n==newed)
return true;
else
return false;
// }
}
int dp[];
int dp2[];

void dabiao(){
dp[] = ;
dp[] = -;
dp2[] = ;
for(int i = ;i<*1e6+;i++)
{
dp[i] += dp[i-]+isPrime(i);
dp2[i] += dp2[i-]+isHuiwen(i);
}
}
int main()
{
int t;
int b , a;
dabiao();
scanf("%d",&t);

 for(int i =  ;i < t;i++)  
 {  
 //    cnt = 0;  
     int sum = ;  
     scanf("%d%d",&b,&a);  
     for(int j = ;j<\*1e6+;j++){  
     ///    vector<int> prime = Prime(j);  
     //     cnt = prime.size();  
         if(a\*dp\[j\]<=b\*dp2\[j\])//b\*Prime(n)<=a\*huiwen(n)  
         sum = j;

     }  
         if(sum)  
         printf("%d\\n",sum);  
         else  
         printf("No");  
 }  

}