資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++ 中素數 n 模 n 的原根
在這個問題中，我們給定一個素數 N。我們的任務是列印素數 N 模 N 的原根。
原根是指素數 N 的一個整數 x，它位於 [1, n-1] 之間，使得 xk (mod n) 的所有值（其中 k 位於 [0, n-2] 之間）都是唯一的。
讓我們舉個例子來理解這個問題，
Input: 13 Output: 2
為了解決這個問題，我們必須使用一個稱為尤拉函式的數學函式。
尤拉函式是 1 到 n 之間與 n 互質的數字的數量。
如果 GCD (i, n) = 1，則數字 i 與 n 互質。
在解決方案中，如果 x 模 n 的乘法階等於尤拉函式，則該數字是原根，否則不是。我們將檢查所有互質數。
注意：素數n 的尤拉函式 = n-1
下面的程式碼將展示我們解決方案的實現，
示例
#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
更新於: 2020年2月3日
1K+ 瀏覽量
廣告