从 1 到 N 有多少对 LCM = N？
From 1 to N how many pairs have LCM = N?
假设N = 8。有4对(1,8),(2,8),(4,8),(8,8)的LCM为8。如果N = 6。则有5对(1,6),(2,6),(2,3),(3,6),(6,6)，LCM为6。现在我想知道如何快速找到对数？
math.stackexchange.com 处的问题 "Pairs of numbers with at given LCM" 给出了公式
((2e1+1)(2e2+1)...(2ek+1)+1)/2
where e1, e2, ... is the exponents for the unique prime factors of n
这个号码。
即
8 = 2^3 有 ((2*3+1)+1)/2 = 4 个这样的对，
6 = 2^1 * 3^1 有 ((2*1+1)(2*1+1)+1)/2 = 5 个这样的对，并且
60 = 2^2 * 3^1 * 5^1 有 ((2*2+1)(2*1+1)(2*1+1)+1)/2 = 23 个这样的对。
你可以参考这里的类似问题
https://math.stackexchange.com/questions/4152/pairs-of-numbers-with-a-given-lcm
基本上如果 n=(p1^e1)(p2^e2)...(pk^ek) 其中 pi 是 1<=i<=k
的素数
那么解决方案将是 ((2e1+1)(2e2+1)...(2ek+1)+1)/2
假设N = 8。有4对(1,8),(2,8),(4,8),(8,8)的LCM为8。如果N = 6。则有5对(1,6),(2,6),(2,3),(3,6),(6,6)，LCM为6。现在我想知道如何快速找到对数？
math.stackexchange.com 处的问题 "Pairs of numbers with at given LCM" 给出了公式
((2e1+1)(2e2+1)...(2ek+1)+1)/2
where e1, e2, ... is the exponents for the unique prime factors of n
这个号码。
即
8 = 2^3 有 ((2*3+1)+1)/2 = 4 个这样的对，
6 = 2^1 * 3^1 有 ((2*1+1)(2*1+1)+1)/2 = 5 个这样的对，并且
60 = 2^2 * 3^1 * 5^1 有 ((2*2+1)(2*1+1)(2*1+1)+1)/2 = 23 个这样的对。
你可以参考这里的类似问题
https://math.stackexchange.com/questions/4152/pairs-of-numbers-with-a-given-lcm
基本上如果 n=(p1^e1)(p2^e2)...(pk^ek) 其中 pi 是 1<=i<=k
的素数
那么解决方案将是 ((2e1+1)(2e2+1)...(2ek+1)+1)/2