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;
  }
}