本文从WordPress迁移而来, 查看全部WordPress迁移文章
uva 10892 LCM Cardinality
给出n,有多少对(a,b)使得a与b的lcm是n,其中(a,b),(b,a)视为一对
找出n所有的约数,枚举两个约数,L <= R, 计算lcm(L,R) = n 则计数
1 |
|
其他OJ : http://218.5.5.242:9018/JudgeOnline/problem.php?id=1111
A与B的gcd是x,设
A = x * a
B = x * b
a与b一定互质
A与B的lcm是y,则
x a b = y
a * b = y / x = n
所以a和b都是n的因数,且a与b互质,一个二次循环暴力枚举即可
(a,b)(b,a)视为两组
1 |
|
hdu 4497
题意:给出gcd和lcm,问存在多少种x,y,z,使得它们的gcd和lcm和给出的数值相等,例如(1,1,2),(1,2,1),(2,1,1)算3种情况
从质因子的角度分析,就拿sample 1来说
6 = 2 x 3
72 = 2^3 x 3^2
- 对于质因子2,可以确定,x,y,z,分解出来的2的个数都一定 >= 1 , 如果三者中有其中一个分解出来的2的个数小于1,最后gcd会小于6
- 对于质因子2,可以确定,x,y,z中至少存在一个,分解出来的2的个数 = 1,否则的话,x,y,z分解出来的2的个数都大于1,最后gcd会大于6
- 对于质因子2,可以确定x,y,z分解出来的2的个数都一定 <= 3 , 如果三者中有其中一个分解出来的2的个数大于3,最后lcm会大于72
- 对于质因子2,可以确定x,y,z中,至少存在一个,分解出来的2的个数 = 3,否则的话,x,y,z分解出来的2的个数都小于3,最后lcm会小于72
假设x,y,z分别分解出nx,ny,nz个2,nx,ny,nz都减掉1个2(表示约掉gcd里面的那一个2),变为nxx,nyy,nzz
可以知道nxx,nyy,nzz中至少有一个为1-1=0,至少有一个为3-1=2(这是根据前面的分析得到的,至少存在一个分解2的个数为1,减掉了1个就是0;至少存在一个分解2的个数为3,减掉1个就是2)
那么可以分为3种种类
1 | 0 0 2 |
推广开,如果这个质因子最多的个数为r,可分为3类
1 | 0 0 r |
又因为(1,1,2),(1,2,1)被视为不同的答案,那么要考虑排列
1 | 0 0 r , 0 r 0 , r 0 0 3种 |
一共 3 + 3 + 6 (r-1) = 6 r 种
所以对于一种因子,能产生6 * r种可能,每种因子都是这样算,最后乘法原理
例子:
gcd = 18 = 2^1 x 3^2
lcm = 6912 = 2^4 x 3^3 x 4^2
对于因子2,r = 4-1 = 3,产生 6 * 3 = 18种
对于因子3,r = 3-2 = 1,产生 6 * 1 = 6种
对于因子4,r = 2-0 = 2,产生 6 * 2 = 12种
最后答案 18 6 12 = 1296
1 |
|