AT_abc142_d [ABC142D] Disjoint Set of Common Divisors

题目描述

给定正整数 $A$ 和 $B$。

从 $A$ 和 $B$ 的所有正公约数中选择若干个。

但要求所选的任意两个不同的整数必须互质。

最多能选择多少个整数？

公约数是指整数 $d$ 同时整除整数 $x$ 和整数 $y$。

互质是指整数 $x$ 和 $y$ 的正公约数只有 $1$。

整除是指存在整数 $\alpha$ 使得 $y = \alpha x$。

输入格式

输入以以下格式从标准输入读入。

$A$ $B$

输出格式

输出满足条件的可选整数个数的最大值。

样例 1

输入

12 18

输出

3

样例 2

输入

420 660

输出

4

样例 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$。

由 ChatGPT 4.1 翻译