D - Disjoint Set of Common Divisors /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

正整数 A, B が与えられます。

AB の正の公約数の中からいくつかを選びます。

ただし、選んだ整数の中のどの異なる 2 つの整数についても互いに素でなければなりません。

最大でいくつ選べるでしょうか。

公約数とは

整数 d が整数 x と整数 y の公約数であるとは、dxy をともに割り切ることをいいます。

互いに素とは

整数 x, y が互いに素であるとは、x, y の正の公約数が 1 のみであることをいいます。

割り切るとは

整数 x が整数 y を割り切るとは、y = \alpha x なる整数 \alpha が存在することをいいます。

制約

  • 入力は全て整数である。
  • 1 \leq A, B \leq 10^{12}

入力

入力は以下の形式で標準入力から与えられる。

A B

出力

条件を満たすように選べる整数の個数の最大値を出力せよ。


入力例 1

12 18

出力例 1

3

1218 の正の公約数は 1, 2, 3, 6 です。

122331 は互いに素なので、1, 2, 3 を選ぶことができ、このときが最大です。


入力例 2

420 660

出力例 2

4

入力例 3

1 2019

出力例 3

1

12019 の正の公約数は 1 しかありません。

Score : 400 points

Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Constraints

  • All values in input are integers.
  • 1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.


Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.


Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.