← 返回题目列表

AtCoder · abc142_d

D. 不相交的公约数集

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给定的是正整数 A 和 B.

让我们选择一些正公约数 A 和 B.

此处,任何两个选定的约数必须是互质的。

我们最多可以选择多少个除数?

公约数的定义

一个整数 d 据说是整数的公约数 x 和 y 当 d 将两者分开 x 和 y.

互质的定义

整数 x 和 y 被称为互质,当 x 和 y 没有正公约数,除了 1.

除法的定义

一个整数 x 据说可以除另一个整数 y 当存在整数时 \alpha 这样 y = \alpha x.

约束

  • 输入中的所有值都是整数。
  • 1 \leq A, B \leq 10^{12}

输入

输入由标准输入按以下格式给出:

A B

输出

打印可以选择满足条件的最大除数数。


示例输入 1

12 18

示例输出 1

3

12 和 18 有以下正公约数: 1, 2, 3,和 6.

1 和 2 互质, 2 和 3 互质,并且 3 和 1 互质,所以我们可以选择 1, 2,和 3,达到最大结果。


示例输入 2

420 660

示例输出 2

4

示例输入 3

1 2019

示例输出 3

1

1 和 2019 没有正公约数,除了 1.