CF 568A(Primes or Palindromes?-暴力推断)
3 seconds
256 megabytes
standard input
standard output
Rikhail Mubinchik believes that the current definition of prime numbers is obsolete as they are too complex and unpredictable. A palindromic number is another matter. It is aesthetically pleasing, and it has a number of remarkable properties. Help Rikhail to
convince the scientific community in this!
Let us remind you that a number is called prime if it is integer larger than one, and is not divisible by any positive integer other than itself and one.
Rikhail calls a number a palindromic if it is integer, positive, and its decimal representation without leading zeros is a palindrome, i.e. reads the same from left to right and right to left.
One problem with prime numbers is that there are too many of them. Let's introduce the following notation: π(n) — the number of primes
no larger than n, rub(n) —
the number of palindromic numbers no larger than n. Rikhail wants to prove that there are a lot more primes than palindromic ones.
He asked you to solve the following problem: for a given value of the coefficient A find the maximum n,
such that π(n) ≤ A·rub(n).
The input consists of two positive integers p, q,
the numerator and denominator of the fraction that is the value of A (, ).
If such maximum number exists, then print it. Otherwise, print "Palindromic tree is better than splay tree" (without the quotes).
1 1
40
1 42
1
6 4
172
能够发现不可能无解,极限情况n不大
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
bool is_prime(int x)
{
if (x==1) return 0;
Fork(i,2,sqrt(x))
{
if (x%i==0) return 0;
}
return 1;
}
const int MAXN =10000000;
int P[MAXN],siz=0,b[MAXN]={0};
void make_prime(int n)
{
Fork(i,2,n)
{
if (!b[i])
{
P[++siz]=i;
}
For(j,siz)
{
if (P[j]*i>n) break;
b[P[j]*i]=1;
if (i%P[j]==0) break;
}
}
}
bool is_pal(int x)
{
char s[10];
sprintf(s,"%d",x);
int p=0,q=strlen(s)-1;
while(p<q) if (s[p]!=s[q]) return 0;else ++p,--q;
return 1;
} bool B[MAXN]={0};
bool make_pal(int n)
{
char s[20];
For(i,10000)
{ sprintf(s,"%d",i);
int m=strlen(s);
int p=m-1;
for(int j=m;p>-1;j++,p--) s[j]=s[p]; int x;
sscanf(s,"%d",&x);
if (x<=n) B[x]=1; for(int j=m;j<=2*m-1;j++) s[j]=s[j+1];
sscanf(s,"%d",&x);
if (x<=n) B[x]=1; }
} int main()
{
// freopen("A.in","r",stdin);
// freopen(".out","w",stdout);
int p,q;
cin>>p>>q;
make_prime(MAXN-1);
make_pal(MAXN-1);
int x1=0,x2=0,n=MAXN-1,ans=1,t=1;
For(i,n)
{
if (i==P[t]) x1++,t++;
if (B[i]) x2++;
if ((ll)(x1)*q<=(ll)(x2)*p) ans=i;
}
cout<<ans<<endl;
return 0;
}
最新文章
- sphinx通过增量索引实现近实时更新
- Spring(1)
- 跨平台的.NET运行环境 Mono 3.2发布
- WinForm中新开一个线程操作 窗体上的控件(跨线程操作控件)
- IBM Rational AppScan 无法记录登录序列 分类: 数据安全 2015-03-18 16:46 158人阅读 评论(0) 收藏
- matlab各格式数据读取与保存函数
- u3d动态加入模型
- spark.SecurityManager: SecurityManager: authentication disabled
- 點擊按鈕后彈出新頁面導致原頁面CSS失效
- JavaScript的事件对象_键盘事件
- ASP.NET2.0中对TextBox的Enable和ReadOnly属性的限制
- iOS iphone5屏幕适配 autosizing
- 【BZOJ2330】 [SCOI2011]糖果
- SGU 101.Domino (欧拉路)
- java的CalssLoader
- VMware workstation转到vsphere解决办法
- 洛谷.5284.[十二省联考2019]字符串问题(后缀自动机 拓扑 DP)
- 2019OO第一单元作业总结
- java.lang.RuntimeException: Unable to instantiate org.apache.hadoop.hive.metastore.HiveMetaStoreClient
- liunx 安装mysql数据库