Rikhail Mubinchik believes that the current definition of prime numbers is obsolete as they are too complex and unpredictable. A palindromic number is another matter. It is aesthetically pleasing, and it has a number of remarkable properties. Help Rikhail to convince the scientific community in this!
Let us remind you that a number is called prime if it is integer larger than one, and is not divisible by any positive integer other than itself and one.
Rikhail calls a number a palindromic if it is integer, positive, and its decimal representation without leading zeros is a palindrome, i.e. reads the same from left to right and right to left.
One problem with prime numbers is that there are too many of them. Let's introduce the following notation: π(n) — the number of primes no larger than n, rub(n) — the number of palindromic numbers no larger than n. Rikhail wants to prove that there are a lot more primes than palindromic ones.
He asked you to solve the following problem: for a given value of the coefficient A find the maximum n, such that π(n) ≤ A·rub(n).
The input consists of two positive integers p, q, the numerator and denominator of the fraction that is the value of A (
, 
).
If such maximum number exists, then print it. Otherwise, print "Palindromic tree is better than splay tree" (without the quotes).
1 1
40
1 42
1
6 4
172
题目大意：设$\pi\left(n\right)$为不超过n的质数的个数，$rub\left(n\right)$为不超过n的回文数的个数。给出两个数p，q，求满足$\pi\left(n\right)=\frac{p}{q}\times rub\left(n\right)$的最小整数n。
据说可以根据输入范围算出答案不会超过$2\times10^6$，然而我是看数据发现最大的输出是1179858，所以直接暴力枚举n计算就行了。注意答案没有单调性，不能二分。
代码在此。
评论 (0)
