0

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

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))
4

1 回答 1

0

尝试所有整数对[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，每次乘以 2 加 1。

请注意，某些解决方案会按对称计算两次。这必须解决。

于 2014-12-15T11:03:42.353 回答