====== Rasterized Lines ======

===== 풀이 =====
  * {{myicon>g2}} [[ps:problems:boj:3614]]와 같은 문제인데, 수의 범위만 더 커진 문제이다.
  * 동일한 방법으로 풀되, N의 모든 약수를 찾을 때와 오일러 피 함수를 계산할 때에, 소인수분해를 나이브한 방법대신에, 폴라드로 알고리즘을 이용해서 빠르게 처리해주기만 하면 된다.
  * 문제에서 주어지는 수는 모두 약수의 개수가 K(=47)개 이하라고 되어있다. 그래서 시간복잡도는 N의 모든 약수를 구하는 것은 소인수 분해에 필요한 O(n^1/4)이고, 모든 약수에 대해서 오일러 피 함수를 계산하는 것은 O(K*n^1/4), 총 O(K*n^1/4)에 해결된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 23362. Rasterized Lines".

- Problem link: https://www.acmicpc.net/problem/23362
- Solution link: http://www.teferi.net/ps/problems/boj/23362

Tags: [number theory]
"""

from teflib import numtheory
from teflib import psutils


@psutils.run_n_times
def main():
    _blank = input()
    N = int(input())

    answer = sum(numtheory.euler_phi(g + 1) for g in numtheory.all_divisors(N))
    print(answer)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency:
    * [[:ps:teflib:numtheory#euler_phi_small|teflib.numtheory.euler_phi]]
    * [[:ps:teflib:numtheory#all_divisors_small|teflib.numtheory.all_divisors]]

{{tag>BOJ ps:problems:boj:플래티넘_1}}