10858 Unique Factorization

題目說明

給一個數字，輸出他的因數分解的組合數量，再以字典序輸出這些組合(每一個組合都是排序的)，例如 輸入30會輸出 4(總共4種組合) 2 3 5 2 15 3 10 5 6 輸入測資直到測資為0，每一筆測資都只有一個數字

解題思路

用遞迴的方法解決，30的因數是2,3,5,6,10,15 recursive(30)= 2recursive(30/2)+3recursive(30/3)+5recursive(30/5)+6recursive(30/6)+... 但是我們只需要由大到小的排列 6*recursive(30/6)這個組合，recursive(5)所有數字都比6小，所以6之後所有的因數都不用計算

總結只需要計算 2recursive(30/2)+3recursive(30/3)+5*recursive(30/5) 準確來說，只需要計算小於或等於sqrt(30)的因數

套用到其他數字就是 假設n的小於或等於sqrt(n)的因數為a0,a1,...,ak; recursive(n)=a0 _ recursive(n/a0)+ ... +ak _ recursive(n/ak)

#include<iostream>
using namespace std;
static int k;
void rec(int d,int n,int total,string p,string& ans,int& per) {
	if(total==k&&p!=" "+to_string(k)&&p.length()>1){
		ans+=p.substr(1)+"\n";
		per++;
	}
	for(int i=d;i<=n;i++) {
		if(n%i==0)
			rec(i,n/i,total*i,p+" "+to_string(i),ans,per);
	}
}
int main() {
	int n;
	while(cin>>n&&n) {
		k=n;
		string s;
		int per=0;
		rec(2,n,1,"",s,per);
		cout<<per<<endl;
		cout<<s;
	}
}