#16. 数字冒险之旅

数字冒险之旅

题目背景

冒险家 fervor_w 在遗迹中发现刻有数字的神秘石板,旁边还刻着奇怪的符号 gcdgcd 。研究古籍后,他得知只有找出石板数字与 gcdgcd 代表数值的最大公约数,才能解开通往宝藏的密码。

fervor_w 日夜钻研,尝试用辗转相除法、分解质因数等方法计算。过程中,他遇到了许多难题,甚至一度陷入困境,但始终没有放弃。终于,在不断尝试与验证后,他成功算出了最大公约数,他简直是当代欧几里德!

fervor_w 将答案输入机关,古老的石门缓缓打开,里面藏着珍贵的文物和失传的知识。这次冒险让 fervor_w 深刻体会到,最大公约数不仅是破解密码的关键,更是探索未知世界的有力工具。

题目描述

给定 abca、b、c ,请你求出

$gcd(\frac{a}{gcd(a,c)},\frac{b}{gcd(b,a)},\frac{c}{gcd(b,c)})$

gcd(a,b)gcd(a,b)a,ba,b 的最大公约数,可以通过欧几里德算法求出

给出欧几里德算法的递归代码

int euclid(int a,int b)
{
  return b==0?a:euclid(b,a%b);
}

这段代码能够在 log2(max(a,b))log_{2}(max(a,b)) 时间复杂度内求出两个数的最大公因数

多组测试用例

输入格式

第一行两个整数 TT ,代表测试样例数。1T1051\leq T \leq 10^{5}

接下来 TT 行 每行 33 个整数 a,b,ca,b,c1a,b,c10501\leq a,b,c\leq 10^{50}

输出格式

对于每个询问,输出一个整数表示答案。

每个答案占一行。

输入输出样例 #1

输入 #1

1
2 2 2

输出 #1

1

说明/提示

提示

由于输入的数字过大,请考虑用别的数据类型输入