정수론1 [Python] 백준 11689 GCD(n, k) = 1 문제 링크 : https://www.acmicpc.net/problem/ 1. 문제 설명 어떤 수가 주어지면, 그 수의 약수를 구하거나 찾거나 활용해야 한다. 대부분의 경우, 그리고 코딩 테스트에 등장하는 문제는 에라토스테네스의 체를 활용하는 정도인데, 백준에서는 그 이상의 지식이 필요한 문제가 종종 있다. 이 문제도 결론을 먼저 말하자면, 오일러 피 함수를 사용해야 한다. 2. 문제 풀이 풀이 코드 : Python 우선 오일러 피 함수를 알아보자. 오일러 피 함수는, 어떤 정수가 주어졌을 때, 그 정수보다 더 작은 수 중에서 서로소인 수의 개수를 알아낼 수 있는 함수이다. 함수는 다음과 같이 계산할 수 있고, 이 값을 계산하기 위해서는 n의 약수가되는 소수를 발견해야 한다. for i in range(.. 2022. 12. 2. 이전 1 다음
