Codeforces Round #315 (Div. 2)――C. Primes or Palindromes? - c++编程基础

TOP

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

2015-11-21 00:55:25 来源: 作者: 【大中小】浏览:1次

Tags：Codeforces Round #315 Div. Primes Palindromes

这道题竟然是一个大暴力。。。

题意：

π(n)：小于等于n的数中素数的个数

rub(n) :小于等于n的数中属于回文数的个数

然后给你两个数p，q，其中A=p/q；然后要你找到对于给定的A，找到使得π(n)?≤?A·rub(n) 最大的n。

（A<=42)

思路：

首先我们可以暴力算出当n为大概150万左右的时候，π(n)大概是 rub(n) 的42倍。

所以我们只需要for到150万左右就好，因为对于后面的式子，肯定能在150万的范围内找到一个n使得这个式子成立的。

而且，我们可以得出因为素数的增长速度肯定是大于回文数的增长速度的，所以我们肯定能够保证这个式子是成立的。

所以，按理说应该不存在impossible的情况。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            using namespace std; #define maxn 2000020 int flag[maxn],num[maxn]; int pal[maxn]; int gcd(int a,int b){ if(b!=0) return gcd(b,a%b); else return a; } void getprime(){ fill(num,num+1+maxn,1); num[0]=num[1]=0; int t=0; for(int i=2;i<=maxn;i++){ if(num[i]){ for(int j=2*i;j<=maxn;j+=i){ num[j]=0; } } num[i]+=num[i-1]; } } bool judge(int n){ int t=0; while(n){ pal[t++]=n%10; n=n/10; } for(int i=0;i
           
            ?
            ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 1532 Drainage Ditches 增广..	下一篇：HDOJ 5375 Gray code DP

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: