黑妹的游戏I-裴蜀定理

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

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

思路:得到的数一定是黑妹的游戏I-裴蜀定理,那么要方程有解,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;
}

 

上一篇:m序列 MATLAB仿真


下一篇:Java垃圾回收器和实现机制