테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 정사각형 ======

===== 풀이 =====
  * 변의 길이가 axb인 직사각형의 대각선이 지나는 정사각형의 개수는 a+b-gcd(a,b) 이다 ([[ps:tutorial:gcd#최대공약수의_활용]] 참고)
  * 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의 개수는 [[ps:tutorial:오일러 피 함수]] φ(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) 밖에 없으므로 쉽게 처리가능하다.


===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency:
    * [[:ps:teflib:numtheory#euler_phi_small|teflib.numtheory.euler_phi_small]]
    * [[:ps:teflib:numtheory#all_divisors_small|teflib.numtheory.all_divisors_small]]

{{tag>BOJ ps:problems:boj:골드_2}}