Trong bài toán này, chúng ta được cho một số nguyên tố N. Nhiệm vụ là in ra nguyên gốc nguyên thủy (primitive root) của số nguyên tố N modulo N.
Nguyên gốc nguyên thủy của số nguyên tố N là một số nguyên x nằm trong [1, n-1] sao cho tất cả các giá trị của xk (mod n) với k trong [0, n-2] là duy nhất.
Hãy xem ví dụ sau để hiểu rõ vấn đề:
Input: 13 Output: 2
Để giải quyết, ta sử dụng hàm toán học gọi là Hàm Euler Totient.
Hàm Euler Totient là đếm các số từ 1 đến n nguyên tố cùng nhau với n.
Một số i nguyên tố cùng nhau với n nếu GCD(i, n) = 1.
Trong giải pháp, nếu bậc nhân của x modulo n bằng hàm Euler Totient, thì x là nguyên gốc nguyên thủy, ngược lại thì không. Ta kiểm tra đối với tất cả các số nguyên tố cùng nhau.
Lưu ý: Hàm Euler Totient của số nguyên tố n = n-1
Đoạn mã dưới đây minh họa triển khai giải pháp:
Ví dụ
#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<<" Nguyên gốc nguyên thủy nhỏ nhất của "<<n<<" là "<<findPrimitiveRoot(n); return 0; }Kết quả
Nguyên gốc nguyên thủy nhỏ nhất của 13 là 2