A7580. [ABC142D] Disjoint Set of Common Divisors
编程题
普及/提高-
知识点
题目描述
给定正整数 $A$ 和 $B$。
从 $A$ 和 $B$ 的所有正公约数中选择若干个。
但要求所选的任意两个不同的整数必须互质。
最多能选择多少个整数？
公约数是指整数 $d$ 同时整除整数 $x$ 和整数 $y$。
互质是指整数 $x$ 和 $y$ 的正公约数只有 $1$。
整除是指存在整数 $\alpha$ 使得 $y = \alpha x$。
从 $A$ 和 $B$ 的所有正公约数中选择若干个。
但要求所选的任意两个不同的整数必须互质。
最多能选择多少个整数？
公约数是指整数 $d$ 同时整除整数 $x$ 和整数 $y$。
互质是指整数 $x$ 和 $y$ 的正公约数只有 $1$。
整除是指存在整数 $\alpha$ 使得 $y = \alpha x$。
输入格式
输入以以下格式从标准输入读入。
> $A$ $B$
> $A$ $B$
输出格式
输出满足条件的可选整数个数的最大值。
输入输出样例
输入 #1
12 18
输出 #1
3
输入 #2
420 660
输出 #2
4
输入 #3
1 2019
输出 #3
1
说明/提示
### 限制条件
- 输入均为整数。
- $1 \leq A, B \leq 10^{12}$
### 样例解释 1
$12$ 和 $18$ 的正公约数为 $1, 2, 3, 6$。$1$ 和 $2$、$2$ 和 $3$、$3$ 和 $1$ 互质，因此可以选择 $1, 2, 3$，这是最大值。
### 样例解释 3
$1$ 和 $2019$ 的正公约数只有 $1$。
- 输入均为整数。
- $1 \leq A, B \leq 10^{12}$
### 样例解释 1
$12$ 和 $18$ 的正公约数为 $1, 2, 3, 6$。$1$ 和 $2$、$2$ 和 $3$、$3$ 和 $1$ 互质，因此可以选择 $1, 2, 3$，这是最大值。
### 样例解释 3
$1$ 和 $2019$ 的正公约数只有 $1$。