중첩 된 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) 

실제로 숫자를 계산 할 필요가 없습니다, countin 그것들은 충분하다. 보다 일반적으로, 해답의 수는 모든 요인의 다양성의 곱으로 n이고, 각 시간은 2 + 1입니다.

일부 솔루션은 대칭으로 두 번 계산됩니다. 이 문제는 해결해야합니다.