/ Vijos / 题库 /

反公约数

反公约数

时间限制:1秒  内存限制:256M


【问题描述】

  输入 2 个正整数 \(p,q\) ,求出满足下列条件的 \(a,b\) 的个数,条件:

  1、\(a,b\) 是正整数
  2、要求 \(a,b\) 以 \(p\) 为最大公约数,以 \(q\) 为最小公倍数。

  试求:满足条件的所有可能的 2 个正整数的个数。

【输入格式】

  含一行两个用一个空格分开的正整数 \(p\) 和 \(q\) 。

【输出格式】

  如果有符合条件的解,则输出多行,每行包含两个用一个空格分开的整数,表示 \(a\) 和 \(b\) 的值。最后一行输出方案数。

【输入输出样例】

 Input

12 2

 Output

2 12
4 6
6 4
12 2
4

【数据限制】

  对于 \(50\%\) 数据:\(2 ≤ p,q ≤ 10,000\);
  对于 \(100\%\) 的数据:\(2 ≤ p,q ≤ 10,000,000\)。

【来源】

 Mr.he

信息

ID
1228
难度
2
分类
数论 | 搜索 | 枚举 点击显示
标签
递交数
4
已通过
1
通过率
25%
被复制
5
上传者