Codeforces Round #315 (Div.1) A Solution
Difference between en1 and en2, changed 9 character(s)
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;}//reservotate x↵
  if(k==x)return true;↵
  else return false;↵
}↵
~~~~~↵
So the code is O(n)↵
↵
Thanks.↵
↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MedalPluS 2015-08-12 18:55:17 9 Tiny change: 'x/=10;}//reserve x\n if(' -> 'x/=10;}//rotate x\n if('
en1 English MedalPluS 2015-08-12 18:31:15 827 Initial revision (published)