3967. 最大公约数

【题目描述】

我们定义两个正整数 $a,b$ 的最大公约数为最大的能同时整除 $a$ 和 $b$ 的正整数，用 $\gcd(a,b)$ 表示。例如，$\gcd(4,6)=2,\gcd(5,7)=1$。

给你两个正整数 $a,b$，你需要找到一个正整数 $x$，使得 $\gcd(a,x)=\gcd(a,b)$ 且 $\gcd(x,b)=\gcd(a,b)$。

为了避免输出过大，你需要保证 $x<2^{64}$。

【输入格式】

输入共一行，题目中的两个正整数 $a,b$。

【输出格式】

输出共一行一个正整数 $x$，表示你给出的答案，注意 $x$ 必须小于 $2^{64}$。

如果有多个解，输出任意一个都可以，你只需要保证你给出的 $x$ 满足题目要求且小于 $2^{64}$。

【样例1输入】

2 3

【样例1输出】

1

【样例2输入】

9 12

【样例2输出】

15

【样例3输入】

30 48

【样例3输出】

42

【样例4输入】

2009 519

【样例4输出】

2024

【样例说明】

样例一中 $a=2,b=3,\gcd(a,b)=1$，输出的 $x=1$ 满足条件，因为 $\gcd(a,x)=\gcd(x,b)=\gcd(a,b)=1$；此外，输出 $5,233,923,9523$ 也是合法的答案。

样例二中 $a=9,b=12,\gcd(a,b)=3$，输出的 $x=15$ 满足条件，因为 $\gcd(a,x)=\gcd(x,b)=\gcd(a,b)=3$；

样例三中 $a=30,b=48,\gcd(a,b)=6$，输出的 $x=42$ 满足条件，因为 $\gcd(a,x)=\gcd(x,b)=\gcd(a,b)=6$；

样例四中 $a=2009,b=519,\gcd(a,b)=1$，输出的 $x=2024$ 满足条件，因为 $\gcd(a,x)=\gcd(x,b)=\gcd(a,b)=1$；

【数据规模与约定】

对于 $100\%$ 的数据，$1\le a,b\le 10^{18}$。

【提示】

你可以使用__gcd(a, b)来获取变量a和b的最大公约数，比如：

int d = __gcd(a, b);

前提是你加载了algorithm头文件或万能头文件。

【来源】

2024年校际联合邀请赛 入门组-第1场 Task1