순환고리1 [C/C++] 프로젝트 오일러 #26 : 순환고리 이번 문제는 가장 긴 순환고리를 찾는 문제입니다. 사실 순환고리는 오일러의 수 문제로 귀결됩니다. 오일러수는 다음과 같은 형태로 정의해서 낼 수 있습니다.\[ n = \prod_{p_k \mid n} p_k^{a_k} \]라고 한다면, 오일러의 수는\[ \phi(n) = \prod_{p_k \mid n} (p - 1)p^{a_k - 1} \]이라고 할 수 있습니다.즉, n이 합성수라고 한다면, 오일러의 수는 엄청나게 줄어들게 됩니다. n이 소수라면 n-1 이 오일러의 수가 됩니다.가장 긴 순환고리를 찾기 위해서는 사실 오일러의 수만 가지고 판단할 수는 없습니다. 10이란 숫자를 가지고 10이 n의 원시근이면 오일러의 수와 동일한 순환고리를 가지겠지만, 원시근이 아니라면, 오일러의 수의 약수 중 .. 2015. 2. 27. 이전 1 다음
