HDU 2964 Prime Bases

解决这题思路就是从找到的合适的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