

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正整数 A, B が与えられます。
A と B の正の公約数の中からいくつかを選びます。
ただし、選んだ整数の中のどの異なる 2 つの整数についても互いに素でなければなりません。
最大でいくつ選べるでしょうか。
公約数とは
整数 d が整数 x と整数 y の公約数であるとは、d が x と y をともに割り切ることをいいます。
互いに素とは
整数 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
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 しかありません。
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.