사용자 도구

사이트 도구


ps:problems:boj:11689

GCD(n, k) = 1

ps
링크https://www.acmicpc.net/problem/11689
출처BOJ
문제 번호11689
문제명GCD(n, k) = 1
레벨골드 1
분류

정수론

시간복잡도O(sqrt(n))
인풋사이즈n<=10^12
사용한 언어Python
제출기록30840KB / 132ms
최고기록76ms
해결날짜2022/06/02

풀이

  • 오일러 피 함수값을 계산하는 문제. 오일러 피 함수 참고.
  • 소인수분해를 이용해서 O(sqrt(n))에 계산 가능하다.

코드

"""Solution code for "BOJ 11689. GCD(n, k) = 1".

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

Tags: [Number theory]
"""

from teflib import numtheory


def euler_phi(n):
    for p in numtheory.prime_factorization_small(n):
        n -= n // p
    return n


def main():
    n = int(input())
    print(euler_phi(n))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
F L W O U
 
ps/problems/boj/11689.txt · 마지막으로 수정됨: 2022/06/02 08:33 저자 teferi