• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	
            
		
			


            

            隨筆 - 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 閱讀(349) 評論(1)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				
            
					# re: PKU 3005 Exploding CPU  回復  更多評論
					  
				
            
				寫的什么程序啊 看都看不懂
				
            
					2009-07-03 15:14 | ddd
				
            
			
            
		

            





            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



国产精品久久久久久久|
久久精品亚洲福利|
久久精品国产亚洲AV麻豆网站|
久久精品亚洲中文字幕无码麻豆|
久久久久免费看成人影片|
秋霞久久国产精品电影院|
无码8090精品久久一区|
97久久综合精品久久久综合|
久久久精品久久久久特色影视|
久久综合给合久久国产免费|
久久久久综合中文字幕|
国产精品一久久香蕉国产线看|
中文字幕久久亚洲一区|
91精品国产91热久久久久福利|
国产A三级久久精品|
久久亚洲国产精品五月天婷|
精品永久久福利一区二区|
久久精品视频一|
精品久久久久久无码国产|
国产V亚洲V天堂无码久久久|
久久99热这里只频精品6|
久久久99精品成人片中文字幕|
久久99精品国产99久久6男男|
久久久久亚洲av综合波多野结衣|
国产午夜电影久久|
欧美精品一区二区精品久久|
97久久超碰国产精品2021|
久久久久亚洲AV无码网站|
色综合久久久久久久久五月|
亚洲国产天堂久久久久久|
国产精品成人无码久久久久久
|
久久99热这里只有精品国产|
久久精品国产亚洲网站|
久久精品九九亚洲精品天堂|
97久久综合精品久久久综合|
99久久精品国产高清一区二区|
伊人久久大香线蕉av不卡|
久久久一本精品99久久精品88|
jizzjizz国产精品久久|
久久精品国产99国产精偷
|
久久久无码精品亚洲日韩蜜臀浪潮|