[BOJ][Python] 백준 29537번 - Большая сумма

문제 링크: https://www.acmicpc.net/problem/29537

---

문제 풀이

오일러 피 함수, 유클리드 호제법, 정수론

 

지문에서 간단하게 $\sum\limits_{d|n}{\sum\limits_{i = 1}^n{\mathrm{gcd}(d, i)}}$만 구하면 된다고 적혀져있다. 하지만 $n$은 $10^{12}$이므로 나이브하게 돌아가진 않을거니 식 정리를 해야한다. 먼저 시그마를 바꿔치기 해보자. $$ \sum_{i=1}^{n} \left( \sum_{d \mid n} \gcd(d, i) \right) $$

이제 $\sum_{d \mid n} \gcd(d, i)$를 잘 변환하면 된다.

우리는 약수 $d$를 고정하고 계산하는게 아니라 $i$를 고정하고 약수 $d$를 바꿔가며 푸는 것으로 바뀐다.

그러면 저 안의 값이 약수 $d$와 $i$의 최대공약수를 묻고 있는데, \( \gcd(d, i) \) 값이 같으면 $\sum_{d \mid n} \gcd(d, i)$ 값도 같아지는 것을 알 수 있다. 따라서 같은 값들은 묶어내고 계산하면 된다. 구체적으로 $n$의 약수인 $d$에 대해 $ \gcd(n, i) = d$를 만족하는 $i$가 몇 개인지 찾아주고 $d$일 때의 $\sum_{d \mid n} \gcd(d, i)$ 값만 찾아주면 된다.

 

$ \gcd(n, i) = d$를 만족하는 $i$의 개수는 간단하게 $\phi( \frac{n}{d} )$로 나타낼 수 있다. 마찬가지로 $\sum_{g \mid n} \gcd(g, d)$ 값을 구하면 된다. 이건 그냥 직접 구해줘도 된다. 이렇게 구하면 식은 다음과 같다. $$ \sum_{d \mid n} \phi\left(\frac{n}{d}\right) \times \left( \sum_{g \mid n} \gcd(g, d) \right) $$

 

최종적으로 우리는 $n$을 소인수분해하여 약수 $d$를 모두 구하고, 반복문으로 $\phi( \frac{n}{d} )$와 $\sum_{g \mid n} \gcd(g, d)$의 값을 곱해주면 된다. 시간 복잡도는 대략 \( O\left( \sqrt{n} + D \left( \sqrt{n} + D \log n \right) \right) \) (\( D \)는 \( n \)의 약수의 개수).

코드