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.↵
↵
↵
↵
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;}//r
if(k==x)return true;↵
else return false;↵
}↵
~~~~~↵
So the code is O(n)↵
↵
Thanks.↵
↵
↵
