程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> HDU 2964 Prime Bases

HDU 2964 Prime Bases

編輯:關於C

解決這題思路就是從找到的合適的base開始,從大到小逐個計算其系數。
為什麼可以這樣設計算法:
1、題目給出n = a0 + a1*p0 + a2*p0*p1 + a3*p0*p1*p2 + ... ,說明對於輸入的每一個n都可分解完,這是前提。
2、代碼中有函數deal()。它完成兩部分功能,第一就是找到合適的base,這個base是不大於輸入的n的,下一個base是要大於n的。因為大於n的base其系數肯定
為0,所以不用處理。
3、那麼,為什麼可以用deal()中的第二個for循環來得到每個base的系數呢?
這取決於每個base的特點:1、2、2*3、2*3*5、2*3*5*7、2*3*5*7*11...。比如n=123,它的最大base為2*3*5,我們用n%(2*3*5)得到到值一定小於7!這又是為啥呢?
如果大於7,那麼最大的base最小也得是2*3*5*7啦!這就證明了開始的處理是正確的。那麼,我們再假設計算到第k個base時是正確的。我們會有經過第k個base處理
後的數據一定小於第k個base,假設第k個base為2*3*5*7*11,處理後n=(2*3*5*7)*(0---11)。這就說明了第k-1個base的處理也一定是正確的!
4、至於輸出可參考output()函數。
5、細心的讀者可能會發現數組a已經溢出了,可是並不影響結果,因為計算時根本用不到那部分。題目會輸入的數據只是32位的。
 
AC代碼:
[cpp]
#include<iostream> 
using namespace std; 
 
const int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47,51,53,57,59};   //前20個素數  
__int64 a[21];  //存放各個base,比如1、2*3、2*3*5、2*3*5*7...  
int b[21],rem;   //數組存放各個base的個數,rem記錄輸入的數據不小於前一個base,小於後一個base的位置  
 
void init()   //計算各個base  

     a[0]=1; 
     for(int i=1;i<=20;i++) 
     { 
         a[i]=a[i-1]*prime[i-1]; 
     } 

 
void deal(int n)  //找到位置並計算每個base的個數  

     int i; 
     for(i=0;i<=20;i++) 
     { 
         if(a[i]<=n && a[i+1]>n) 
         { 
              rem=i; 
              break; 
         }    
     } 
      
     memset(b,0,sizeof(b)); 
     for(i=rem;i>=0;i--) 
     { 
         b[i]=n/a[i]; 
         n=n%a[i]; 
     } 

 
void output(int n)  //輸出  

     cout<<n<<" = "; 
     for(int i=0;i<=rem;i++) 
     { 
         if(b[i]) 
         { 
             cout<<b[i]; 
             for(int j=0;j<i;j++) 
             { 
                  cout<<"*"<<prime[j]; 
             }  
              
             if(i!=rem)           
                cout<<" + "; 
         } 
     } 
     cout<<endl; 

                        
int main() 

    init(); 
     
    int n; 
    while(cin>>n,n) 
    { 
        deal(n); 
         
        output(n); 
    } 
     
    return 0; 

 


摘自 ON THE WAY

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved