加速嵌套lcm计算

Question

我怎样才能加快计算速度。我尝试了一些减少计算的方法，但没有任何效果。

long long pairsFormLCM( int n ) {
    long long res = 0;
    for( int i = 1; i <= n; i++ )
        for( int j = i; j <= n; j++ )
           if( lcm(i, j) == n ) res++; // lcm means least common multiple
    return res;
}

我不希望这里有任何代码。解决的想法或解释是必需的。

Expected run time: O(sqrt(N))

Answer 1

尝试[1,n]中的所有整数对实在是太过分了。您应该考虑n并计算这些因素的所有产品，以便至少有一个产品达到所需的多重性。(两个整数的lcm是它们的所有素因子的乘积，每个因子都具有最大的多重性。)

示例：

对于n=1500=2².3.5³，下列多重性将起作用：

For 2, 5 combinations: (0,2), (1,2), (2,2), (2,1), (2,0)
For 3, 3 combinations: (0,1), (1,1), (1,0)
For 5, 7 combinations: (0,3), (1,3), (2,3), (3,3), (3,2), (3,1), (3,0)

总的来说，5.3.7 = 105解决方案：

(1.1.1,2².3.5³), (2.1.1,2².3.5³), (2².1.1,2².3.5³), (2².1.1,2.3.5³), (2².1.1,1.3.5³),
(1.3.1,2².3.5³), (2.3.1,2².3.5³), (2².3.1,2².3.5³), (2².3.1,2.3.5³), (2².3.1,1.3.5³),
(1.3.1,2².1.5³), (2.3.1,2².1.5³), (2².3.1,2².1.5³), (2².3.1,2.1.5³), (2².3.1,1.1.5³),
(1.1.5,2².3.5³), (2.1.5,2².3.5³), (2².1.5,2².3.5³), (2².1.5,2.3.5³), (2².1.5,1.3.5³),
(1.3.5,2².3.5³), (2.3.5,2².3.5³), (2².3.5,2².3.5³), (2².3.5,2.3.5³), (2².3.5,1.3.5³),
(1.3.5,2².1.5³), (2.3.5,2².1.5³), (2².3.5,2².1.5³), (2².3.5,2.1.5³), (2².3.5,1.1.5³),
(1.1.5²,2².3.5³), (2.1.5²,2².3.5³), (2².1.5²,2².3.5³), (2².1.5²,2.3.5³), (2².1.5²,1.3.5³),
(1.3.5²,2².3.5³), (2.3.5²,2².3.5³), (2².3.5²,2².3.5³), (2².3.5²,2.3.5³), (2².3.5²,1.3.5³),
(1.3.5²,2².1.5³), (2.3.5²,2².1.5³), (2².3.5²,2².1.5³), (2².3.5²,2.1.5³), (2².3.5²,1.1.5³),
(1.1.5³,2².3.5³), (2.1.5³,2².3.5³), (2².1.5³,2².3.5³), (2².1.5³,2.3.5³), (2².1.5³,1.3.5³),
(1.3.5³,2².3.5³), (2.3.5³,2².3.5³), (2².3.5³,2².3.5³), (2².3.5³,2.3.5³), (2².3.5³,1.3.5³),
(1.3.5³,2².1.5³), (2.3.5³,2².1.5³), (2².3.5³,2².1.5³), (2².3.5³,2.1.5³), (2².3.5³,1.1.5³),
(1.1.5³,2².3.5²), (2.1.5³,2².3.5²), (2².1.5³,2².3.5²), (2².1.5³,2.3.5²), (2².1.5³,1.3.5²),
(1.3.5³,2².3.5²), (2.3.5³,2².3.5²), (2².3.5³,2².3.5²), (2².3.5³,2.3.5²), (2².3.5³,1.3.5²),
(1.3.5³,2².1.5²), (2.3.5³,2².1.5²), (2².3.5³,2².1.5²), (2².3.5³,2.1.5²), (2².3.5³,1.1.5²),
(1.1.5³,2².3.5), (2.1.5³,2².3.5), (2².1.5³,2².3.5), (2².1.5³,2.3.5), (2².1.5³,1.3.5),
(1.3.5³,2².3.5), (2.3.5³,2².3.5), (2².3.5³,2².3.5), (2².3.5³,2.3.5), (2².3.5³,1.3.5),
(1.3.5³,2².1.5), (2.3.5³,2².1.5), (2².3.5³,2².1.5), (2².3.5³,2.1.5), (2².3.5³,1.1.5),
(1.1.5³,2².3.1), (2.1.5³,2².3.1), (2².1.5³,2².3.1), (2².1.5³,2.3.1), (2².1.5³,1.3.1),
(1.3.5³,2².3.1), (2.3.5³,2².3.1), (2².3.5³,2².3.1), (2².3.5³,2.3.1), (2².3.5³,1.3.1),
(1.3.5³,2².1.1), (2.3.5³,2².1.1), (2².3.5³,2².1.1), (2².3.5³,2.1.1), (2².3.5³,1.1.1)

没有必要实际计算这些数字，计算它们就足够了。更普遍地说，解的数目是n的所有因子的乘积，每乘二加一。

请注意，一些解决方案被计算了两次，对称。这个必须修好。