题目链接:http://120.78.162.102/problem.php?id=6248
时间限制: 1 Sec  内存限制: 128 MB

题目描述

质数定义为在大于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”

样例输入

2
1 1
4 6

样例输出

40
16

解题思路

我们可以估算出最大的n，当a=1，b=10000的时候，打表出来我们发现会到达2e6，所以我们可以从1~2e6开始判断，判断到新的满足要求的n就更新。我们用素筛打一个表，然后判断一个数是不是回文，最后就是直接暴力判断就行了。

#include <stdio.h>
const int N = 2e6 + 10;
int a[N], b[N], isprime[N];
bool edge(int n)
{
    int ans = n, num = 0;
    while (n)
    {
        num = num * 10 + n % 10;
        n /= 10;
    }
    if (num != ans)
        return 0;
    return 1;
}
void prime()
{
    for (int i = 2; i < N; i++)
        isprime[i] = 1;
    for (int i = 2; i * i < N; i++)
        for (int j = i + i; j < N; j += i)
            isprime[j] = 0;
}
void init()
{
    prime();
    a[1] = 0;
    b[1] = 1;
    for (int i = 2; i < N; i++)
    {
        a[i] = a[i - 1] + isprime[i];
        b[i] = b[i - 1] + edge(i);
    }
}
int main()
{
    init();
    int t, m, n;
    scanf("%d", &t);
    while (t--)
    {
        int maxl = 0;
        scanf("%d%d", &m, &n);
        for (int i = 1; i < N; i++)
            if (a[i] * n <= b[i] * m)
                maxl = i;
        printf("%d\n", maxl);
    }
    return 0;
}