이 문제에서 소수 N이 주어집니다. 우리의 임무는 소수 N 모듈로 N의 원시근을 출력하는 것입니다.
기본 루트 소수 N의 는 k가 [0, n-2]에 있는 xk(mod n)의 모든 값이 고유하도록 [1, n-1] 사이에 있는 정수 x입니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
Input: 13 Output: 2
이 문제를 해결하려면 오일러의 토티엔트 함수라는 수학 함수를 사용해야 합니다. .
오일러의 Totient 함수는 숫자 n에 대해 상대적으로 소수인 1에서 n까지의 숫자의 개수입니다.
숫자 i는 GCD(i, n) =1인 경우 상대적으로 소수입니다.
솔루션에서 x modulo n의 승법 차수가 오일러의 Totient Function과 같으면 숫자는 원시근이고 그렇지 않은 경우에는 그렇지 않습니다. 모든 상대 소수를 확인합니다.
참고:소수 n=n-1의 오일러 Totient 함수
아래 코드는 우리 솔루션의 구현을 보여줍니다.
예시
#include<bits/stdc++.h>
using namespace std;
bool isPrimeNumber(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
int power(int x, unsigned int y, int p) {
int res = 1;
x = x % p;
while (y > 0){
if (y & 1)
res = (res*x) % p;
y = y >> 1;
x = (x*x) % p;
}
return res;
}
void GeneratePrimes(unordered_set<int> &s, int n) {
while (n%2 == 0){
s.insert(2);
n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i+2){
while (n%i == 0){
s.insert(i);
n = n/i;
}
}
if (n > 2)
s.insert(n);
}
int findPrimitiveRoot(int n) {
unordered_set<int> s;
if (isPrimeNumber(n)==false)
return -1;
int ETF = n-1;
GeneratePrimes(s, ETF);
for (int r=2; r<=ETF; r++){
bool flag = false;
for (auto it = s.begin(); it != s.end(); it++){
if (power(r, ETF/(*it), n) == 1){
flag = true;
break;
}
}
if (flag == false)
return r;
}
return -1;
}
int main() {
int n= 13;
cout<<" Smallest primitive root of "<<n<<" is "<<findPrimitiveRoot(n);
return 0;
} 출력
Smallest primitive root of 13 is 2