链接:https://www.nowcoder.com/acm/contest/130/A来源:牛客网
2
3 2 1
6 5 4
输出
0
3
实际上我们可以得到的数字一定只可能是某个数的倍数,因为最终黑板上的数字一定是ax+by+cz 这样的形式。考虑更相减损术的过程,可以发现能得到的最小数字为gcd(a,b,c),然后把max(a,b,c)不停的减这个数字就可以得到所有的数字啦。
#include<bits/stdc++.h> using namespace std; long long gcd(long long a,long long b) { return b==0 ? a:gcd(b,a%b); } int main() { int t;cin>>t; while(t--) { long long a,b,c,ans;cin>>a>>b>>c; long long vis=gcd(a,gcd(b,c)); cout<<max(a/vis,max(b/vis,c/vis))-3<<endl; } return 0; }