最大公约数和最小公倍数问题

最大公约数和最小公倍数问题

题目背景

你会求 gcd\gcdlcm\operatorname{lcm} 吗?那么 \cdots \cdots

题目描述

已知 a,ba,b,求有多少组满足条件的 正整数 x,yx,y 使得:

gcd(x,y)=a\gcd(x,y) = a 并且 lcm(x,y)=b\operatorname{lcm}(x,y) = b.

注意:(x,y)(x,y)(y,x)(y,x) 算作两组。(若 xyx \not = y

输入格式

一行两个数 a,ba,b,空格隔开。

输出格式

一行,方案数。

输入样例

3 60

输出样例

样例解释

(3,60),(12,15),(15,12),(60,3)(3,60) , (12,15) , (15,12) , (60,3),共 44 组。

数据范围

对于 30%30 \% 的数据,a,b102a,b \leq 10^2.
对于 60%60 \% 的数据,a,b103a,b \leq 10^3.
对于 80%80 \% 的数据,a,b105a,b \leq 10^5.
对于 100%100 \% 的数据,1a,b1061 \leq a,b \leq 10^6a,ba,b 均为 正整数

信息

ID
1003
难度
3
分类
数论 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者