Codeforces Round #315 (Div. 2)C. Primes or Palindromes?(暴力)

本文主要是介绍Codeforces Round #315 (Div. 2)C. Primes or Palindromes?(暴力)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://codeforces.com/problemset/problem/569/C

 

题目大意：求最大的n满足q*小于等于n的素食个数<=p*小于等于n的回文数个数

 

题目思路：直接暴力，处理好素数表和暴力出回文数，然后1e7到1暴力即可。

以下是代码：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 1e7+5;
const int MOD = 1e9+7;
int p,q,prime[MAXN],pal[MAXN],temp[MAXN],a[MAXN],b[MAXN];
int main()
{memset(prime,0,sizeof(prime));memset(pal,0,sizeof(pal));memset(a,0,sizeof(a));memset(b,0,sizeof(b));prime[1]=1;rep(i,2,MAXN-1){if(prime[i])continue;for(int j=i+i;j<MAXN;j+=i){prime[j]=1;}}rep(i,1,MAXN-1){int p=i,num=0;while(p){temp[num++]=p%10;p/=10;}int flag=0;rep(j,0,num/2){if(temp[j]!=temp[num-j-1]){flag=1;break;}}if(!flag)pal[i]=1;}rep(i,1,MAXN){a[i]=a[i-1]+(prime[i]^1);b[i]=b[i-1]+pal[i];}while(~scanf("%d%d",&p,&q)){int ans=0;per(i,MAXN-1,1){if((ll)q*a[i]<=(ll)p*b[i]){ans=i;break;}}cout<<ans<<endl;}return 0;
}

 

这篇关于Codeforces Round #315 (Div. 2)C. Primes or Palindromes?(暴力)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---