链接：http://codeforces.com/gym/100801
题意：给一个正整数n，将n拆分为若干个数的和，每个数都是型如2^p*3^q，且两两互不整除。
分析：如果n=2^p*3^q，直接输出n；如果n=2^p*3^q*k，k不能被2或3整除，先拆分k，然后再把拆分结果乘2^p*3^q即可；如果n不能被2或3整除，n必然是奇数，然后又不能拆1，所以必然会拆一个3的幂出来，为了避免重复，拆一个尽量大的出来，剩下的是个偶数，递归一下解决。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 const ll maxn=1e18+5; 8 ll ans[1000]; 9 int devide(ll n,ll *a){10 ????ll mu=1;11 ????int cnt=0;12 ????if(n==1){13 ????????a[0]=mu;14 ????????return 1;15 ????}16 ????if(n%2==0||n%3==0){17 ????????while(n%2==0){18 ????????????n/=2;mu*=2;19 ????????}20 ????????while(n%3==0){21 ????????????n/=3;mu*=3;22 ????????}23 ????????if(n==1){24 ????????????a[0]=mu;25 ????????????return 1;26 ????????}27 ????????cnt=devide(n,a);28 ????????for(int i=0;i<cnt;i++)29 ????????????a[i]*=mu;30 ????????return cnt;31 ????}32 ????a[0]=1;33 ????while(a[0]*3<n)a[0]*=3;34 ????cnt=devide(n-a[0],a+1)+1;35 ????return cnt;36 }37 int main(){38 // ???freopen("distribution.in","r",stdin);39 // ???freopen("distribution.out","w",stdout);40 // ???freopen("e:\\in.txt","r",stdin);41 ????ll t,n,m;42 ????cin>>t;43 ????while(t--){44 ????????cin>>n;45 ????????m=devide(n,ans);46 // ???????sort(ans,ans+m);47 ????????cout<<m<<endl;48 ????????for(int i=0;i<m;i++){49 ????????????if(i)cout<<‘ ‘;50 ????????????cout<<ans[i];51 ????????}52 ????????cout<<endl;53 ????}54 ????return 0;55 }GYM 100801 D.Distribution in Metagonia(数论)
原文地址：http://www.cnblogs.com/7391-KID/p/7631569.html