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.

UPD:My English is bad... All of us are fighting for dreams.Maybe I can't reach my dream,but I won't give up. Life is to chanlledge.So try to be "bigger than bigger".

题意：给你一个n*m的矩形，求最少用几个a*a的小矩形去覆盖它？（不允许打碎，但允许覆盖）

算法：数学 手画几个矩形，我们发现，贴着边放矩形即可，如果不能整除则+1，否则累积下来 然后用行乘列，记得开long long 时间复杂度O(1) 空间复杂度O(1)

#include <iostream>
#include <cstdio>

using namespace std;

int a,n,m;
long long row,col;
int main(){
    cin>>n>>m>>a;
    row=n/a+(n%a==0?0:1);
    col=m/a+(m%a==0?0:1);
    cout<<row*col;
    return 0;
}