黑妹的游戏I

题目链接牛客网-16766

题目描述

链接:https://ac.nowcoder.com/acm/problem/16766
来源:牛客网

黑妹最近在玩一个有趣的游戏,游戏规则是这样的:
刚开始黑板上有三个不同的初始数字,然后黑妹每一次可以选择黑板上的两个不同的数字,然后计算出这两个不同数字之差的绝对值,如果黑板上没有这个数字,那么就把这个新数字写在黑板上。
黑妹已经玩腻了这个游戏,现在黑妹想知道她最多能添加多少个数字。
输入描述:
第一行一个整数T表示数据组数。(1≤T≤100000)
接下来T行每行三个整数 a,b,c 表示黑板上的三个初始数字。(1≤a,b,c≤10^18,1≤a,b,c≤10^18)
输出描述:
对于每组数据输出一行表示答案。
示例1
输入
2
3 2 1
6 5 4
输出
0
3

思路

大概是一道思维题? 我们举个例子。

假如初始的三个数字是8 6 4.
我们发现 可以生成的新数字只有2,因为8 6 4这三个数字的共同最大公约数为2, 所以最后的数字只能是 8 - 2 * k;(k < 8 / 2); 这个应该可以理解吧, 所以总共的数字 为 8 / 2 = 4 之前已经有了3个,所以只能新生成1个;

再举个栗子, 8 6 5;
此时的最大公约数为 1;
不难发现,只要我们生成了1, 我们就可以从8 依次减1递推到1; 总个数为 8 / 1
减去之前已经有的3个,答案为5.

通过栗子,不难得出结论;

答案 = 三个数最大的 / 三个数的最大公约数 - 3;

PS:注意数据范围 得开long long

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

#define long long long

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)
{
long a, b, c;
cin >> a >> b >> c;
long MAX = max(a, max(b, c));
long k = __gcd(a, __gcd(b, c));
cout << MAX / k - 3 << endl;
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------