黑妹的游戏I-裴蜀定理

本文主要是介绍黑妹的游戏I-裴蜀定理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://ac.nowcoder.com/acm/problem/16766

大意：给出3个数a，b，c，每次任取两个数作减法，得到的数如果不存在，则加入，然后继续执行操作。

思路：得到的数一定是，那么要方程有解，ans就一定是gcd(a,b,c)的倍数，并且ans要小于max(a,b,c).

//a*x+b*y+c*z = gcd(a,b,c)
#include <bits/stdc++.h>
#define ll long long
const int N = 1e6+7;
const int mod = 1e9+7;
const ll ds = 1e15;
const double eps = 1e-8;

using namespace std;

void solve(){
    int t;
    ll a,b,c,mmax = 0,g1,g2;
    cin >> t;
    while(t--){
        cin >> a >> b >> c;
        mmax = max(a,b);
        mmax = max(mmax,c);
        g1 = __gcd(a,b);
        g2 = __gcd(g1,c);
        cout << mmax/g2-3 << endl;
    }
}

int main(){
    // int t;
    // cin >> t;
    // while(t--)
        solve();
    //system("pause");
    return 0;
}

这篇关于黑妹的游戏I-裴蜀定理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！