Блог пользователя MedalPluS

Автор MedalPluS, история, 9 лет назад, По-английски

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;}//rotate x
  if(k==x)return true;
  else return false;
}

So the code is O(n)

Thanks.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

//reserve x?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by MedalPluS (previous revision, new revision, compare).

»
9 лет назад, # |
Rev. 8   Проголосовать: нравится +5 Проголосовать: не нравится

Your code is actually because of is_palind function.

you can use some kind of sieve to generate all palindromes in O(n). If x is palindrome, then yxy, y0x0y, etc are also palindromes. My somewhat messy submission: 12461876