사용자 도구

사이트 도구


ps:problems:boj:28474

피보나치 서로소

ps
링크acmicpc.net/…
출처BOJ
문제 번호28474
문제명피보나치 서로소
레벨플래티넘 5
분류

수학

시간복잡도O(T*sqrt(n))
인풋사이즈T<=1,000, n<=1,000,000,000
사용한 언어Python 3.11
제출기록31120KB / 164ms
최고기록156ms
해결날짜2024/02/14

풀이

  • 피보나치 수의 최대공약수의 특성은 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()

토론

댓글을 입력하세요:
Y C O X H
 
ps/problems/boj/28474.txt · 마지막으로 수정됨: 2024/02/14 15:26 저자 teferi