0과 1의 쉼터

풀이 euler_phi(x) = n/x가 성립하기 위해서는, n/x가 정수 이여야 한다. 즉, x는 n의 약수이어야 한다. n의 약수들을 모두 구한 후 오름차순으로 정렬해서 최소의 x를 찾아도 되고, 약수를 구해서 바로 계산을 해도된다. O(n^(1/2)) 만에 약수를 구하는 방법을 사용했다. 소스코드 #include #define min(a, b) a < b ? a : b int euler_phi(int n){ int euler = n; for (int p = 2; p*p

풀이 오일러의 정리를 이용해서 풀이하는 문제다. 이나... 자료가 너무 부족하다. 오일러의 정리에 대해 자료를 찾던 도중 다음과 같은 자료를 찾았다. a와 n이 서로소이면, a^m ≡ 1 mod n에서 m = EPF(n)을 만족하는 정수 m이 적어도 하나 존재한다. a (mod n)에 대한 차수가 위 식의 m이 될 수 있다. (N ^ f( N, EPF(M) ) ) % M을 재귀호출해 찍었다. 풀이했다. 입력받거나 전달받은 N과 M 둘 중 하나가 1일 때, 1을 반환해주면 위 식의 계산에 따라 원하는 결과를 얻을 수 있다. 단, 제곱을 구하는 과정에서 long long으로도 담을 수 없는 수가 나온다. (N^(N^N)) mod M != (N^((N^N) mod M)) mod M 이므로, M이 아닌 EPF(..

풀이 "백준 11689, GCD(n, k) = 1"를 이용해 풀이했다. 시간초과는 발생하지 않으니 그냥 0을 입력받을 때까지 반복하면된다. 소스코드 #include int main(){ long long n; while (1){ scanf("%lld", &n); if (!n) break; long long euler = n; for (long long p = 2; p*p

풀이 Euclidean algorithm을 사용해 풀이할 수 있지만, 최대 10^12의 수들에 대해 계산을 해야하므로 시간제한에 걸린다. Euler product formula을 사용해 쉽게 풀이할 수 있다. 나누어 떨어지는 소인수(p)를 찾아 Euler product formula에 적용시키면 된다. p-1 / p (= 1- 1/p)를 n에 곱해주어야 한다. p로 먼저 나눈 후 p-1을 곱해주자. for (long long p = 2; p*p