Disjoint Set of Common Divisors

题目描述

给定正整数 $A$ 和 $B$。 我们从 $A$ 和 $B$ 的正公约数中选择若干个数。 这里，任意两个被选择的约数必须互质。 最多我们可以选择多少个约数？

输入格式

输入按以下格式从标准输入给出： $A$ $B$

输出格式

输出满足条件时可选择的约数的最大个数。

12 18

3

420 660

4

1 2019

1

提示

输入中的所有数值均为整数。 $1 \leq A, B \leq 10^{12}$$12$ 和 $18$ 的正公约数如下：$1$、$2$、$3$ 和 $6$。 $1$ 和 $2$ 互质，$2$ 和 $3$ 互质，$3$ 和 $1$ 互质，所以我们可以选择 $1$、$2$ 和 $3$，这达到最大结果。
$1$ 和 $2019$ 除了 $1$ 之外没有正的公约数。

标签: AtCoder|abc142D

来源

AtCoder|abc142D