[分治演算法]因式分解
- 2019 年 10 月 13 日
- 筆記
整數因子分解問題
http://acm.sdut.edu.cn/onlinejudge2.dev/index.php/Home/Index/problemdetail/pid/1722.html
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
大於1的正整數n可以分解為：n=x1*x2*…*xm。例如，當n=12 時，共有8 種不同的分解式：
12=12；
12=6*2；
12=4*3；
12=3*4；
12=3*2*2；
12=2*6；
12=2*3*2；
12=2*2*3。
對於給定的正整數n，計算n共有多少種不同的分解式。
12=12；
12=6*2；
12=4*3；
12=3*4；
12=3*2*2；
12=2*6；
12=2*3*2；
12=2*2*3。
對於給定的正整數n，計算n共有多少種不同的分解式。
Input
輸入數據只有一行，有1個正整數n (1≤n≤2000000000)。
Output
將計算出的不同的分解式數輸出。
Sample Input
12
Sample Output
8
演算法一（超時）
演算法思路：
比如以 12為例，情況1）與 情況2）都應該計算在Count中，但情況2)是根據情況1)產生的。因此需要遞歸，每層函數對i進行遍歷一遍，如果temp/i==0，說明該層的數可以被分解，再遞歸進入下一層。
程式碼：
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 int Count; 6 7 // 來計算整數因子分解問題 8 void func(int temp) { 9 10 for (int i = 2; i < temp; i++) { 11 if (temp%i == 0) { 12 Count++; 13 func(temp / i); 14 } 15 } 16 } 17 18 int main() { 19 20 Count = 0; 21 int temp; 22 cin >> temp; 23 func(temp); 24 cout << Count+1 << endl; 25 }
演算法二（優化）
演算法一存在的弊端：我們求(i,temp/i）中 temp/i 的因式分解個數時，會重複計算(如下圖）
解決演算法一的策略：我們採用一個數組直接存儲數字6的因子，如果發現該arr[6]中存在數，則直接用避免重複計算。
演算法思路：
依然採用遞歸，t = i * j，則 count(t) = count(i) + count(j)；為避免重複計算 (t = i * j = j * i)，應該限制 i < j，即 for(i;i<sqrt(t);i++)。
