4992：互质子集
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 互质子集
## 题目描述
在一次数学竞赛中，小 $A$ 需要从两个正整数 $A$ 和 $B$ 的**正公约数集合中**选择一些数构成子集，且要求子集中的数两两之间必须是**互质**的。
请编程求出找出满足条件的**互质子集**中最多有多少个整数？
这里给出上述描述中，相关数学概念的定义。
- **公约数：**正整数 $d$ 是整数 $x$ 和 $y$ 的公约数，意味着 $d$ 能同时整除 $x$ 和 $y$ 。比如： $12$ 和 $15$ 的正公约数有： $1, 3$ 。
- **互质：**两个整数 $x$ 和 $y$ 是互质的，意味着它们的最大公约数为 $1$ 。比如： $8$ 和 $25$ 满足互质的关系。
- **互质子集：**从 $A$ 和 $B$ 的正公约数集合中，选出若干个数，使得这若干个数两两之间互质。比如： $12$ 和 $18$ 的互质子集，可以选择： $1,2,3$ 三个整数。
## 输入格式
输入两个正整数 $A$ 和 $B$ 。
## 输出格式
输出一个整数，表示可以选择的互质子集中的最多有多少个整数。
## 样例
### 样例输入 1
```text
20 60
```
### 样例输出 1
```text
3
```
### 样例输入 2
```text
600 1200
```
### 样例输出 2
```text
4
```
### 样例输入 3
```text
37800000000 94500000000
```
### 样例输出 3
```text
5
```
## 说明/提示
样例 $1$ 说明
$20$ 和 $60$ 的公约数为 $1, 2, 4, 5, 10, 20$ 。在这些公约数中， $1, 2, 5$ 互质，所以最大可以选择的数量是 $3$ 。
数据范围
本题共有 $25$ 个测评数据。
有 $2$ 个测评数据，满足 $A, B$ 两数互质。
有 $4$ 个测评数据，满足 $1 \leq A,B \leq 3000$ 。
对于 $100\%$ 的数据，满足 $1 \leq A, B \leq 10^{12}$ 。
---
**题目来源：** 25年3月-B组（才俊）