题解：B4463 [海淀区入门组 2025] 素数和回文数

luogu_LiuShaRui · 2026-01-24 08:22:59 · 题解

题解：B4463 [海淀区入门组 2025] 素数和回文数

link

思路

看到题目，我们不难想到 O(n^2) 的做法，但是 n 最高能到 10^6 的级别，肯定超时。我们可以使用埃拉托斯特尼筛法，将复杂度优化到 O(n \log n) 的做法，因为要考虑回文数。

提示点

1. 质数的时候不能判断 1。
2. 因为要判断最大值，通过暴力算法以及计算，只需要枚举的 2 \times 10^6 即可。

   code

   #include<bits/stdc++.h>
   #define int long long
   using namespace std;
   bool is_palindrome(int a){
   int b=a;
   int ans=0;
   while(b){
       ans*=10;
       ans+=b%10;
       b/=10;
   }
   return a==ans;
   }
   int f[2000005];
   void init_sieve(){
   memset(f,0,sizeof(f));
   f[0]=f[1]=1;
   for(int i=2;i<=2000000;++i){
       if(f[i]==0){
           for(int j=i*2;j<=2000000;j+=i){
               f[j]=1;
           }
       }
   }
   }
   bool is_prime(int a){
   return f[a]==0;
   }
   signed main(){
   int p,q;
   cin>>p>>q;
   int z=0,h=0;
   int max2=0;
   init_sieve();
   for(int i=1;i<=2000000;++i){
       if(is_palindrome(i))h++;
       if(i!=1&&is_prime(i))z++;
       if(z*q<=h*p){
           max2=max(max2,i);
       }
   }
   cout<<max2;
   return 0;
   }