Codeforces Round 315 (Div. 1)

A. Primes or Palindromes?

https://codeforces.com/contest/568/problem/A

3 seconds / 256 megabytes

standard input / standard output

## Problem

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).

## Input

The input consists of two positive integers p, q, the numerator and denominator of the fraction that is the value of A (, ).

## Output

If such maximum number exists, then print it. Otherwise, print "Palindromic tree is better than splay tree" (without the quotes).

Input

1 1

Output

40

Input

1 42

Output

1

Input

6 4

Output

172

## 题解

$$\pi(x)\sim \frac{x}{\log x}$$

## 代码

#include <bits/stdc++.h>
#define endl '\n'
// #define int long long

using namespace std;

constexpr int MAXN = 2e6 + 10;
bool not_prime[MAXN];
int prime[MAXN], prime_cnt[MAXN], prime_size;

void init_prime()
{
not_prime[0] = not_prime[1] = true;
for (int i = 2; i < MAXN; i++)
{
prime_cnt[i] = prime_cnt[i - 1];
if (!not_prime[i])
{
prime[prime_size++] = i;
prime_cnt[i]++;
}
for (int j = 0; j < prime_size && i * prime[j] < MAXN; j++)
{
not_prime[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
}
}
}

bool check_palindromes(int x)
{
vector<int> digit;
while (x)
{
digit.push_back(x % 10);
x /= 10;
}
for (int i = 0, j = digit.size() - 1; i <= j; i++, j--)
if (digit[i] != digit[j])
return false;
return true;
}

int palindromes_cnt[MAXN];
void init_palindromes()
{
for (int i = 1; i < MAXN; i++)
palindromes_cnt[i] = palindromes_cnt[i - 1] + check_palindromes(i);
}

void solve()
{
init_prime();
init_palindromes();
int p, q;
cin >> p >> q;
for (int i = MAXN - 1; i >= 0; i--)
{
if (prime_cnt[i] * q <= palindromes_cnt[i] * p)
{
cout << i << endl;
return;
}
}
cout << "Palindromic tree is better than splay tree" << endl;
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}