문제:
자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.
출력:
GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.
풀이방법:
https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98
오일러 피 함수 - 위키백과, 우리 모두의 백과사전
오일러 피 함수의 그래프. ϕ(1)부터 ϕ(1000)까지의 값들을 나타낸다. 수론에서 오일러 피 함수(-函數, 영어: Euler’s phi (totient) function)는 정수환의 몫환의 가역원을 세는 함수이다. 즉, n이 양의 정
ko.wikipedia.org
GCD(n,k) = 1 는 n과 k가 서로수임을 의미하는 것이고, n과 서로소인 정수의 갯수를 세는 방법은 정수론에서 오일러 피 함수가 있다.
오일러 피 함수를 간략히 설명하면 다음과 같다. 오일러 피 함수는 주어진 n의 소인수를 구한 뒤에, 각 소인수들의 (1-1/p)를 구해 n에 곱해주면 서로소의 갯수를 구할 수 있다. 따라서 이 함수를 python으로 구현하여 다음과 같이 계산하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
|
n = int(input())
answer = n
for i in range(2, int(n**0.5)+1):
if n%i==0:
while n%i==0:
n //= i
answer *= ((i-1)/(i))
if n > 1:
answer *= 1 - (1 / n)
print(int(answer))
|
cs |
문제링크:
https://www.acmicpc.net/problem/11689
11689번: GCD(n, k) = 1
자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]10164. 격자상의 경로 (0) | 2022.02.22 |
|---|---|
| [BOJ]1916. 최소비용 구하기 (0) | 2022.02.18 |
| [BOJ]2526. 싸이클 (0) | 2022.02.14 |
| [BOJ]2641. 다각형그리기 (0) | 2022.02.11 |
| [BOJ]2660. 회장뽑기 (0) | 2022.02.10 |