Rasterized Lines

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

"""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()

• Dependency:
  • teflib.numtheory.euler_phi
  • teflib.numtheory.all_divisors