algorithm - 1 から N までで、LCM = N であるペアはいくつありますか?

Question

N = 8 と仮定します。最小公倍数が 8 である 4 つのペア (1,8)、(2,8)、(4,8)、(8,8) があります。N = 6 の場合、5 つのペア (1,8) があります。 6),(2,6),(2,3),(3,6),(6,6) で、LCM は 6 です。ペアの数をすばやく見つける方法を知りたいですか?

Answer 1

math.stackexchange.comの質問「与えられた 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 組。