728x90
풀이
euler_phi(x) = n/x가 성립하기 위해서는, n/x가 정수 이여야 한다.
즉, x는 n의 약수이어야 한다.
n의 약수들을 모두 구한 후 오름차순으로 정렬해서 최소의 x를 찾아도 되고, 약수를 구해서 바로 계산을 해도된다.
O(n^(1/2)) 만에 약수를 구하는 방법을 사용했다.
소스코드
#include <stdio.h>
#define min(a, b) a < b ? a : b
int euler_phi(int n){
int euler = n;
for (int p = 2; p*p <= n; p++){
if (n % p == 0) euler = euler/p *(p - 1);
while (n % p == 0) n = n/p;
}
return n == 1 ? euler : euler/n *(n - 1);
}
int main(){
int n, result = 1e9;
scanf("%d", &n);
for (int x = 1; x*x <= n; x++)
if (n % x == 0){
if (euler_phi(x) == n/x) result = min(result, x);
if (euler_phi(n/x) == x) result = min(result, n/x);
}
printf("%d", result == 1e9 ? -1 : result);
}
출처 및 참고자료
19577번: 수학은 재밌어
xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다.
www.acmicpc.net
[백준 11689] GCD(n, k) = 1 [C]
풀이 Euclidean algorithm을 사용해 풀이할 수 있지만, 최대 10^12의 수들에 대해 계산을 해야하므로 시간제한에 걸린다. Euler product formula을 사용해 쉽게 풀이할 수 있다. 나누어 떨어지는 소인수(p)를
kyr-db.tistory.com
[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.
학원 학생들이 약수를 모두 찾는 (또는 약수의 합, 개수를 구하거나, 소수 판별 등등) 코드를 어떻게 짜는지 살펴보면, 백이면 백 \(O(n)\) 알고리즘을 사용한다. 하지만 어떤 수의 모든 약수를 구
doodle-ns.tistory.com
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 11690] LCM(1, 2, ..., n) [C] (0) | 2021.08.30 |
---|---|
[백준 2904] 수학은 너무 쉬워 [C] (0) | 2021.08.30 |
[백준 5615] 아파트 임대 [C] (0) | 2021.08.29 |
[백준 11402] 이항 계수 4 [C] (0) | 2021.08.28 |
[백준 15791] 세진이의 미팅 [C] (0) | 2021.08.28 |