Codeforces Round #315 (Div. 1) A. Primes or Palindromes? 暴力-白红宇

Codeforces Round #315 (Div. 1) A. Primes or Palindromes? 暴力

阅读量：4700 次

发布时间：2019-06-09

本文共 2989 字，大约阅读时间需要 9 分钟。

A. Primes or Palindromes?

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://poj.org/problem?id=3261

Description

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 ( $\text{[math]}$ , $\text{[math]}$ ).

Output

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

Sample Input

1 1

Sample Output

HINT

题意

给你p,q，A=p/q

π(n)表示1-n中素数的个数

rub(n)表示1-n中回文数的个数

求最大的n，满足π(n) ≤ A·rub(n).

题解：

CF测评姬很快，1e7直接上暴力就好了

暴力算出极限数据大概是1.5*1e6的样子，所以1e7很稳

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 10050000#define mod 10007#define eps 1e-9int Num;char CH[20];//const int inf=0x7fffffff; //нчоч╢Сconst int inf=0x3f3f3f3f;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//**************************************************************************************bool flag[maxn];int primes[maxn], pi;int pa[maxn];void GetPrime(){ int i, j; pi = 0; memset(flag, false, sizeof(flag)); for (i = 2; i < maxn; i++) { primes[i]+=primes[i-1]; if (!flag[i]) { primes[i] ++ ; for (j = i; j < maxn; j += i) flag[j] = true; } }}int check_Pa(int x){ int X=x; int x2=0; while(X) { x2*=10; x2+=X%10; X/=10; } return x2==x?1:0;}void GetPa(){ for(int i=1;i
                   
                    >p>>q; double A=p/q; int ans=0; for(int i=1;i
                    
                     =primes[i]*1.0) ans=i; } if(ans==0) cout<<"Palindromic tree is better than splay tree"<

转载于:https://www.cnblogs.com/qscqesze/p/4719862.html

你可能感兴趣的文章