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


	


            
	    
    


            

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

            





            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



精品久久人人爽天天玩人人妻|
亚洲国产欧洲综合997久久|
青青草原综合久久大伊人|
亚洲国产日韩综合久久精品|
三级三级久久三级久久|
97精品伊人久久久大香线蕉|
久久久久女人精品毛片|
国产精品免费久久久久电影网|
亚洲国产天堂久久综合|
久久综合九色综合网站|
久久精品亚洲欧美日韩久久|
久久久久久精品无码人妻|
天天综合久久久网|
无码人妻久久一区二区三区|
国产精品无码久久久久|
热re99久久6国产精品免费|
久久久久18|
久久亚洲欧美日本精品|
国产成年无码久久久免费|
国产精品免费看久久久香蕉
|
色综合久久综合中文综合网|
久久精品一本到99热免费|
色综合合久久天天给综看|
嫩草影院久久99|
久久午夜羞羞影院免费观看|
午夜精品久久影院蜜桃|
久久97久久97精品免视看|
久久精品国产69国产精品亚洲|
久久久久亚洲AV成人片|
狠狠色婷婷久久一区二区|
久久综合偷偷噜噜噜色|
久久久无码精品亚洲日韩软件|
国产成人无码精品久久久免费|
精品久久久久久国产91|
久久国产精品成人片免费|
午夜精品久久久久久毛片|
日韩人妻无码精品久久免费一|
久久精品成人欧美大片|
亚洲伊人久久成综合人影院|
热综合一本伊人久久精品|
亚洲精品无码久久久|