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


	


            
	    
    


            

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

            





            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



99久久精品午夜一区二区|
久久婷婷五月综合97色|
日本精品久久久久中文字幕|
亚洲国产精品热久久|
久久精品国产福利国产琪琪|
亚洲v国产v天堂a无码久久|
性色欲网站人妻丰满中文久久不卡|
97久久香蕉国产线看观看|
久久精品国产一区二区电影|
久久久久久久免费视频|
久久综合九色综合97_久久久|
久久免费观看视频|
久久99免费视频|
亚洲中文字幕无码久久2017|
国产99久久久久久免费看
|
欧美大战日韩91综合一区婷婷久久青草
|
亚洲AV日韩精品久久久久久|
国产毛片久久久久久国产毛片|
中文精品久久久久人妻不卡|
狠狠色综合久久久久尤物|
久久久久国产精品熟女影院|
久久天天躁狠狠躁夜夜av浪潮
|
午夜精品久久影院蜜桃|
9久久9久久精品|
久久综合香蕉国产蜜臀AV|
一本色道久久综合|
亚洲国产精品综合久久网络|
91麻精品国产91久久久久|
日韩精品久久无码中文字幕|
久久天天躁夜夜躁狠狠躁2022
|
av午夜福利一片免费看久久|
亚洲国产日韩欧美综合久久|
久久精品国产精品亚洲艾草网美妙|
国产精品99久久精品|
久久免费的精品国产V∧|
色88久久久久高潮综合影院|
人妻无码中文久久久久专区|
久久精品国产亚洲αv忘忧草|
久久人妻少妇嫩草AV蜜桃|
久久午夜免费视频|
久久久久亚洲AV片无码下载蜜桃|