Codeforces Round #315 (Div.1) A Solution

Правка en1, от MedalPluS, 2015-08-12 18:31:15

I think it's a simple task.

Let's make problem simplely. pi(n)<=A*rub(n) <=>pi(n)<=p/q*rub(n) <=>pi(n)*q<=p*rub(n) So we don't need to use double

We know that Max n <= 2e6 So we can prefix n 1 to 2e6 How to get pi&rub? We can use DP.

for(i=2;i*i<=n;i++)//O(n) get prime
  if(isp[i])
    for(j=i*i;j<=n;j+=i)
      isp[j]=false;
pi[0]=pi[1]=0;//both 1 and 0 isn't prime
for(i=2;i<=n;i++)
  if(isp[i])pi[i]=pi[i-1]+1;//because i is a prime
  else pi[i]=pi[i-1];
for(i=1;i<=n;i++)
  if(is_palind(i))rub[i]=rub[i-1]+1;
  else rub[i]=rub[i-1];
//How to write _is_palind(i)_?
bool is_palind(int x){
  int k=0,tmp=x;
  while(x){k=k*10+x%10;x/=10;}//reserve x
  if(k==x)return true;
  else return false;
}

So the code is O(n)

Thanks.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский MedalPluS 2015-08-12 18:55:17 9 Tiny change: 'x/=10;}//reserve x\n if(' -> 'x/=10;}//rotate x\n if('
en1 Английский MedalPluS 2015-08-12 18:31:15 827 Initial revision (published)