[백준 19577] 수학은 재밌어 [C]

백준 - 19577

---

 

풀이

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번: 수학은 재밌어

[백준 11689] GCD(n, k) = 1 [C]

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.