정사각형

• 변의 길이가 axb인 직사각형의 대각선이 지나는 정사각형의 개수는 a+b-gcd(a,b) 이다 (최대공약수의_활용 참고)
• a+b-gcd(a,b) = N 이 되는 (a,b)의 개수를 구하면 된다.
• gcd(a,b) = g 로 놓고, a=gx, b=gy 로 치환하면, gx+gy-g=N이 되고, 정리하면 x+y = N/g + 1
• N/g가 정수여야 하므로, g는 N의 약수여야 한다. 그러면, N/g 도 N의 약수이다. 결국 모든 N의 약수 m에 대해서, x+y=m+1 이고, 서로 소인 (x,y)쌍을 구하면 된다.
  • x+y=K 이면서 서로소인 (x,y)를 찾는 것은 그냥 x를 1부터 K까지 증가시키면서, gcd(x,K-x)=1 인 x들을 찾으면 O(K)에 구할 수 있다.
  • 하지만, gcd(x,K-x)=gcd(x,K) 이므로, gcd(x,K)==1인 x의 개수는 오일러 피 함수 (Euler's phi function) φ(x)의 값과 같고, 이 값은 O(sqrt(K))에 구할수 있다.
• 그럼 시간복잡도를 정리하면
  • 나이브하게 N의 모든 약수를 구하는 데에는 O(sqrt(N))이 걸리고, 그렇게 구한 약수의 개수는 대략 O(N^1/3)이다.
  • 각 약수에 대해서 O(sqrt(N))에 오일러 피 함수를 계산하므로, 이 부분의 시간복잡도는 O(N^(1/3+1/2)) 가 된다..;
  • 그래서 총 시간복잡도는 대략 O(N^(5/6)) 정도..
• 마지막으로, (x,y)와 (y,x)를 동일하게 취급하므로, 얻어진 개수를 2로 나눠야 한다.
  • 만약 x=y 인 경우가 있다면 이 경우는 2로 나누면 안되는데, x=y 이면서 서로소인 것은 (1,1) 밖에 없으므로 쉽게 처리가능하다.

"""Solution code for "BOJ 3614. 정사각형".

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

Tags: [number theory]
"""

from teflib import numtheory


def main():
    N = int(input())
    count = sum(
        numtheory.euler_phi_small(g + 1)
        for g in numtheory.all_divisors_small(N)
    )
    print((count + 1) // 2)


if __name__ == '__main__':
    main()

• Dependency:
  • teflib.numtheory.euler_phi_small
  • teflib.numtheory.all_divisors_small