#16. 数字冒险之旅
数字冒险之旅
题目背景
冒险家 fervor_w
在遗迹中发现刻有数字的神秘石板,旁边还刻着奇怪的符号 。研究古籍后,他得知只有找出石板数字与 代表数值的最大公约数,才能解开通往宝藏的密码。
fervor_w
日夜钻研,尝试用辗转相除法、分解质因数等方法计算。过程中,他遇到了许多难题,甚至一度陷入困境,但始终没有放弃。终于,在不断尝试与验证后,他成功算出了最大公约数,他简直是当代欧几里德!
当 fervor_w
将答案输入机关,古老的石门缓缓打开,里面藏着珍贵的文物和失传的知识。这次冒险让 fervor_w
深刻体会到,最大公约数不仅是破解密码的关键,更是探索未知世界的有力工具。
题目描述
给定 ,请你求出
$gcd(\frac{a}{gcd(a,c)},\frac{b}{gcd(b,a)},\frac{c}{gcd(b,c)})$
为 的最大公约数,可以通过欧几里德算法求出
给出欧几里德算法的递归代码
int euclid(int a,int b)
{
return b==0?a:euclid(b,a%b);
}
这段代码能够在 时间复杂度内求出两个数的最大公因数
多组测试用例
输入格式
第一行两个整数 ,代表测试样例数。。
接下来 行 每行 个整数 。。
输出格式
对于每个询问,输出一个整数表示答案。
每个答案占一行。
输入输出样例 #1
输入 #1
1
2 2 2
输出 #1
1
说明/提示
提示
由于输入的数字过大,请考虑用别的数据类型输入
相关
在下列比赛中: