A7580 | [ABC142D] Disjoint Set of Common Divisors
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
给定正整数 $A$ 和 $B$。
从 $A$ 和 $B$ 的所有正公约数中选择若干个。
但要求所选的任意两个不同的整数必须互质。
最多能选择多少个整数？
公约数是指整数 $d$ 同时整除整数 $x$ 和整数 $y$。
互质是指整数 $x$ 和 $y$ 的正公约数只有 $1$。
整除是指存在整数 $\alpha$ 使得 $y = \alpha x$。
从 $A$ 和 $B$ 的所有正公约数中选择若干个。
但要求所选的任意两个不同的整数必须互质。
最多能选择多少个整数？
公约数是指整数 $d$ 同时整除整数 $x$ 和整数 $y$。
互质是指整数 $x$ 和 $y$ 的正公约数只有 $1$。
整除是指存在整数 $\alpha$ 使得 $y = \alpha x$。
输入格式
输入以以下格式从标准输入读入。
> $A$ $B$
> $A$ $B$
输出格式
输出满足条件的可选整数个数的最大值。
输入输出样例
输入 #1
12 18
输出 #1
3
输入 #2
420 660
输出 #2
4
输入 #3
1 2019
输出 #3
1
### 限制条件
- 输入均为整数。
- $1 \leq A, B \leq 10^{12}$
### 样例解释 1
$12$ 和 $18$ 的正公约数为 $1, 2, 3, 6$。$1$ 和 $2$、$2$ 和 $3$、$3$ 和 $1$ 互质，因此可以选择 $1, 2, 3$，这是最大值。
### 样例解释 3
$1$ 和 $2019$ 的正公约数只有 $1$。
- 输入均为整数。
- $1 \leq A, B \leq 10^{12}$
### 样例解释 1
$12$ 和 $18$ 的正公约数为 $1, 2, 3, 6$。$1$ 和 $2$、$2$ 和 $3$、$3$ 和 $1$ 互质，因此可以选择 $1, 2, 3$，这是最大值。
### 样例解释 3
$1$ 和 $2019$ 的正公约数只有 $1$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？