解決這題思路就是從找到的合適的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
