ZeroJudge B573: Permutations and Greatest Common Divisor

The Greatest Common Divisor (GCD) refers to the largest common factor among several integers.
In permutation problems, arranging a set of numbers can result in different sequences. For example, for the number 12, there are two permutations: (1) 12 and (2) 21 (sorted from smallest to largest). Similarly, for the number 123, there are six permutations: (1) 123, (2) 132, (3) 213, (4) 231, (5) 312, and (6) 321 (sorted from smallest to largest). For the number 1234, there are 24 permutations, with the sequences as follows:
(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

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains an integer, N, representing the number of test cases, where 2 ≤ N ≤ 5. Each subsequent line contains three positive integers i, j, and k, separated by spaces, representing each test case.

Generate combinations using the value of i, where the set of i values is {12, 123, 1234, 12345, 123456}. Then, sort the combinations in ascending order based on the i value. Find the jth and kth values in the sorted list of combinations, and calculate their greatest common divisor (GCD). The jth and kth values will be present in the list of combinations sorted by the i value.		For each test case, output one line. Output the greatest common divisor (GCD) of the jth and kth values found in the list of combinations sorted by the value of i.
5
12 1 2
123 2 5
1234 15 9
1234 3 4
1234 2 5		3
12
2
2
1
ZeroJudge B573 Sample Test Case

Thought Process

Use DFS to find different combinations of numbers, ensuring that there are no identical numbers in the test data (e.g., 22).

Set up an empty string to store different combinations of numbers and a Map to track which numbers have been added. If the length of the string equals the length of the original string, it can be stored in an array. Otherwise, run a For loop, and if the current character is not already in the Map, call DFS recursively. Update the string with the current character and update the Map. After the call, remember to restore the string and Map.

Once you find two numbers, find all the factors of one of the numbers, then compare each factor with the factors of the other number to see which factors are common.

Sample Code－ZeroJudge B573: Permutations and Greatest Common Divisor

#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
Tags

Related Posts

Comments