2022 Henan Mengxin League game (3): Henan University

J- Magic number

Magic number

Ideas ：

First, analyze the congruence of two numbers ：a ≡ b ( mod x )

We know ：(a - b) / x It must be an integer （ namely 、x | (a - b) ), So just make x by (a - b) The factor of that will do

Secondly, consider the case of three number congruences ： a ≡ b ≡ c ( mod x )

Equivalent to three congruences being established at the same time ：a ≡ b ( mod x ) && b ≡ c ( mod x ) && c ≡ a ( mod x )

Can be launched ( x | (a - b) && x | (b - c) && x | (c - a) )

Three equations hold at the same time , namely 、x by gcd(a-b, b-c, c-a) The factor of （ Is the factor of the greatest common divisor , Then the three equations hold at the same time ）

The code is as follows ：

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5 + 10, M = 1010;
const int mod = 1e9 + 7;

int T;
int n, m, sum;
PII a[N];

void check(int a, int b, int c)
{
    vector<int> v;
    int x = __gcd(abs(a - b), __gcd(abs(b - c), abs(c - a)));

    for(int i = 1; i <= x / i; i ++ )
    {
        if(x % i == 0)
        {
            v.push_back(i);
            if(x / i != i) v.push_back(x / i);
        }
    }
    
    sort(v.begin(), v.end());
    
    for(auto it : v)
        cout << it << " ";
    cout << endl;
    return;
}

void solve()
{
    int a, b, c;
    cin >> a >> b >> c;
    if(a == b && b == c) 
    {
        cout << "-1" << endl;
        return;
    }
    else check(a, b, c);
}

signed main()
{
    cin >> T;
    while(T -- )
        solve();
    
    return 0;
}