最大公因數（Greatest Common Divisor，簡寫為G.C.D.），指某幾個整數共有因數中最大的一個。
在排列組合問題中將一組數字進行排列，可以得到不同的數字順序，例如 12 這個數的排列共有：(1)12、(2)21 二組(由小到排序)；例如123 這個數的排列組合順序為：(1) 123、(2) 132、(3) 213、(4) 231、(5) 312、(6) 321 六組 (由小到排序)；例如 1234 這數的排列組合有 24 組，數列順序如下：
(1) 1234 (2) 1243 (3) 1324 (4) 1342 (5) 1423 (6) 1432
(7) 2134 (8) 2143 (9) 2314 (10) 2341 (11) 2413 (12) 2431
(13) 3124 (14) 3142 (15) 3214 (16) 3241 (17) 3412 (18) 3421
(19) 4123 (20) 4132 (21) 4213 (22) 4231 (23) 4312 (24) 4321
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第 1 列的數字 N 代表有幾筆資料要測試，2 <= N <=5 ，之後每列為每筆的測試資料，共有三個正整數 i、j、k 中間空白隔開。 以 i 這值進行排列組合，i 的集合為{12, 123, 1234, 12345, 123456}，再依 i 值排列組合順序 (由小到大排序)，找出第 j 個和第 k 個的值，再算出個這二個值的最大公因數。第j個和第k 個的值會存在以 i 值排列組合數列中。 | 每筆測試資料輸出一列。輸出以 i 值排列組合順序中，找出第 j 個和第 k 個的值，再算出個這二個值的最大公因數。 |
| 5 12 1 2 123 2 5 1234 15 9 1234 3 4 1234 2 5 | 3 12 2 2 1 |
解題思路
使用 DFS 的方式來找不同組合的數字，測資中不會有相同的數字 (例如：22)。
設定一個空的字串存不同的數字組合、一個 Map 存已經加過哪些數字了。如果字串長度等於原始字串長度就可以將其存到一個陣列中，否則就跑一個 For迴圈，如果目前字元沒有在 Map 中有資料，就再互叫一次 DFS，要先將字串加上目前的字元並且 Map 也要更新，呼叫完之後記得要將字串和 Map 還原。
找到兩個數字之後就找其中一個數字的所有因數，再和另外一個數字一一判斷有哪些因數是相同的。
範例程式碼－ZeroJudge B573: 排列組合、最大公因數
#include <iostream>
#include <vector>
#include <math.h>
#include <map>
using namespace std;
string num;
int one, two, a, b;
vector<int>v;
int toint(string str) {
if (str.length() == 1) return int(str[0] - '0');
return stoi(str);
}
void DFS(string sum, map<char, int>MAP) {
if (sum.length() == num.length()) {
v.push_back(toint(sum));
if (v.size() == a) one = v[a-1];
if (v.size() == b) two = v[b-1];
return;
}
for (int i = 0; i<num.length(); i++) {
if (MAP[num[i]] == 0) {
MAP[num[i]]++;
DFS(sum+num[i], MAP);
MAP[num[i]]--;
}
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i<N; i++) {
v.clear();
cin >> num >> a >> b;
if (a > b) swap(a, b);
string sum = "";
map<char, int>MAP;
DFS(sum, MAP);
vector<int>factor;
for (int j = 1; j<sqrt(one)+1; j++) {
if (one % j == 0) {
factor.push_back(j);
factor.push_back(one/j);
}
}
int ans = 1;
for (int j = 0; j<factor.size(); j++) {
if (two % factor[j] == 0) ans = factor[j];
}
cout << ans << "\n";
}
}
//ZeroJudge B573
//Dr. SeanXD