随笔 - 40, 文章 - 0, 评论 - 19, 引用 - 0
数据加载中……

PKU 3005 Exploding CPU

呵呵 过了这个题目挺高兴
锻炼了 筛法和判断素数的能力
还想了一个关键的枚举剪枝
这个题目我是去枚举题目中的A和第一个素数P1；
然后计算B 幷继续推Pn
对小于1000000的数一次性筛出；
大数用最基本的判断的方式。

  1Source Code
  2
  3Problem: 3005  User: hongtaozhy 
  4Memory: 4244K  Time: 94MS 
  5Language: G++  Result: Accepted 
  6
  7Source Code 
  8#include<stdio.h>
  9#include<math.h>
 10#define SSS 6000
 11#define SIZE 1000000
 12#define INF 2000000000
 13#define NUM 200
 14__int64 aa[300];
 15__int64 rr[50000];
 16int pri[NUM];
 17int sub[SIZE];
 18int pdsu(__int64 n)
 19{    
 20    __int64 i;
 21    if(n<=0||n==1 )
 22        return 0;
 23    if( n==2)
 24        return 1;
 25    else{
 26        for(i=2; i*i<=n; i++)
 27            if(n%i==0)
 28                return 0;
 29    }
 30    return 1;
 31}
 32void sf(){
 33    int temp,n; 
 34    for(int i=0;i<SIZE;i++)
 35       sub[i]=1;        
 36    sub[0]=sub[1]=0;
 37    for(int i=2;i<=sqrt(SIZE);i++){
 38        if(sub[i]==1){
 39           temp=2*i;
 40           while(temp<=SIZE){
 41                 sub[temp]=0;             
 42                 temp+=i;
 43           }
 44        }
 45    }
 46}
 47int  init(){
 48      int j = 0 ;
 49      pri[j++] = 2 ;
 50      pri[j++] = 3 ;
 51      for( int i = 3 ; i<SSS ;i++ ){
 52         if(sub[i]){
 53                     pri[j++]=i;
 54         }
 55      }
 56      return j;
 57}
 58int main(){
 59    int num;
 60    int t = 0 ;
 61    __int64 res , next ,next2 ;
 62  int b;        
 63  sf();      
 64    num = init();   
 65  sf();
 66               for(int a = 1 ; a< 600 ; a++ ){                       
 67                       for(int i = 0; i<NUM ;i++  ){                              
 68                              res = pri[i] ;                             
 69                              b = pri[i] - a;   
 70                              if(b == 0 ) continue;                      
 71                              next = a * pri[i] + b ;
 72                              if(next == pri[i]) continue;
 73                              if(res * next > INF){
 74                                      continue;
 75                                      }
 76                              if(next <0 )
 77                                      continue;
 78                              if(next >= SIZE){                                      
 79                                  if(!pdsu(next))
 80                                      continue ;
 81                              }
 82                             else{
 83                                      if(!sub[next])
 84                                      continue ;
 85                              } 
 86                              res = res * next;
 87                              if(res >INF) continue;
 88                               
 89                            while(1){
 90                               next2 = next * a +b;
 91                               if(next2 == next ) break;
 92                               if(res * next2 > INF){
 93                                      break;
 94                                      }
 95                               if(next2 <0 )
 96                                      break;
 97                             if(next2 >= SIZE){
 98                                      if(!pdsu(next2))
 99                                      break ;
100                              }
101                              else{
102                                      if(!sub[next2])
103                                      break ;
104                              } 
105                              res = res * next2;
106                              if(res >INF) break;
107                              rr[t++] = res ;
108                              next = next2 ;
109                              
110                            }
111                             
112                       }
113               } 
114            
115     for(int i = 0 ; i<t ;i++ )
116             for(int j = i+1 ; j <t ;j++)
117                     {
118                         if(rr[i]>rr[j]){
119                         int temp = rr[i];
120                         rr[i] = rr[j];
121                         rr[j] = temp;
122                         }
123                       
124                     }
125       int ccc = 0;
126      for(int i = 0 ; i <t ; i++)
127     {
128              if(rr[i]!= rr[i+1])    
129              aa[ccc++]=rr[i];
130     }        
131  //    printf("init over\n"); 
132     int N;
133    __int64 zuo ,you ; 
134            scanf("%d",&N);
135               while(N--){
136               scanf("%I64d%I64d",&zuo,&you);
137              
138          int     ans = 0 ;
139         for(int i = 0 ; i <243 ;i++){
140                 if(zuo<=aa[i] && you>=aa[i])
141                ans++;
142         }
143               printf("%d\n",ans);
144               }
145    return 0 ;
146}

posted on 2008-10-06 23:02 hadn't 阅读(326) 评论(1)  编辑 收藏 引用

评论

# re: PKU 3005 Exploding CPU  回复  更多评论   

写的什么程序啊 看都看不懂
2009-07-03 15:14 | ddd

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理