피보나치 서로소

• 피보나치 수의 최대공약수의 특성은 i번째 피보나치수와 j번째 피보나치수의 최대공약수는 gcd(i,j)번째 피보나치수이라는 것이다. 그러면 n번째 피보나치수와 i번째 피보나치수가 서로소가 되려면, gcd(n,i)가 1 또는 2이면 된다
• gcd(n,i)가 1인 i의 개수를 세는 것은, n과 서로소인 n미만인 수의 개수를 세는 것으로, 이것은 간단히 φ(n) 를 계산해 주면 된다. 시간복잡도는 O(n^1/2)
• 이제 gcd(n,i)가 2인 i의 개수를 세자. 우선 n이 2의 배수가 아니라면, 당연히 개수는 그냥 0개이다. n이 2의 배수라면? n=2k 로 두었을때, gcd(k,j)=1 이면 gcd(n,2j)=2 가 될것이다. 따라서 φ(n/2) 를 구해주면 끝.
• 이렇게 오일러 피 함수를 두 번 계산해줘도 시간복잡도는 O(n^1/2)이고 통과하는데에는 전혀 문제가 없지만, 그래도 조금 더 최적화시킬수 있는 여지가 있다. φ(n/2)을 φ(n)으로부터 구해주는 방법이다
• 오일러 피 함수는 곱셈적 함수이므로 n/2가 2의 배수가 아니라면 φ(n) = φ(n/2)*φ(2) = φ(n/2) 가 성립한다. n/2가 2의 배수라면, 우선 n=2^k*x로 나눠 써보자. φ(n) = φ(2^k)φ(x) = 2^(k-1)*φ(x)이고, φ(n/2) = φ(2^(k-1))φ(x) = 2^(k-2)*φ(x) 이므로, φ(n) = 2*φ(n/2)가 된다.

"""Solution code for "BOJ 28474. 피보나치 서로소".

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

Tags: [math]
"""

import sys
from teflib import numtheory


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        n = int(sys.stdin.readline())

        if n == 1:
            answer = 0
        elif n == 2:
            answer = 1
        else:
            answer = numtheory.euler_phi(n)
            if n % 4 == 0:
                answer += answer // 2
            elif n % 2 == 0:
                answer += answer

        print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.euler_phi