题解 | 等式填充问题

#include <bits/stdc++.h>
using namespace std;

bool check(int a, int b) { //辗转相除法求出a，b最大公约数，也可以用递归写 
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    if (a == 1)
        return true;
    else
        return false;
}

int main() {
    int arr[9] {1, 2, 3, 4, 5, 6, 7, 8, 9};
    do {
        int a = arr[0] * 10 + arr[1], c = arr[2];
        int d = arr[3] * 10 + arr[4], f = arr[5];
        int g = arr[6] * 10 + arr[7], i = arr[8];
        if (c == 1 || f == 1 || i == 1) //排除分母为1的情况 
            continue;
        if (!check(a, c) || !check(d, f) || !check(g, i)) //排除分母和分子最大公约数不为1的情况 
            continue;
        if (a * f * i + d * c * i == g * c * f) //由于next_permutation是按字典序全排列，可以直接输出 
            cout << a << '/' << c << '+'
                 << d << '/' << f << '=' << g << '/' << i << endl;
    } while (next_permutation(arr, arr + 9)); //全排列列出所有情况 
}