728x90 피 함수1 [python] 백준 11689 GCD(n, k) = 1 https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 n의 약수 중 소수인 것을 $p_{1}, p_{2}, ... p_{a}$ 라 할 때 소수의 개수는 다음과 같이 구할 수 있다. $\phi$ (n) = n $\times \prod_{i=1}^{a} (1-\frac{1}{p_{i}})$ 시간초과가 나지 않게 리스트를 사용하지 않고 for문을 돌면서 소수를 찾으면 ans -= ans/p 를 한 다음 n에서 소수 p의 흔적을 없앤다. p를 약수로 갖지 않을 때 까지 계속 나눠준다는 것이다... 2023. 2. 24. 이전 1 다음 728x90
