資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢素數模的原根數量。
在這個問題中，我們給定一個素數 N。我們的任務是查詢素數模的原根數量。
數字的原根 - 它是一個小於 N 的數字 (r)，對於 [0, n-2] 範圍內的所有 X，它都具有所有不同的 r^x(mod N) 值。
讓我們舉個例子來理解這個問題，
Input : N = 5 Output : 2
解決方案方法
解決此問題的一個簡單方法是基於試探法。我們將檢查從 2 到 (N-1) 的所有數字，以滿足 x 範圍為 [0, n-2] 的條件，並在找到滿足條件的值時中斷。
這種解決方案很簡單，易於實現，但解決方案的時間複雜度為 N2 階。如果 N 的值很大，這可能會導致執行時間過長。
因此，解決此問題的一個更有效的解決方案是使用尤拉函式 φ(N)
因此，對於一個數字 r 成為 N 的原根。它對 N 的模的乘法階數等於 φ(N)。以下是需要遵循的步驟 -
我們需要找到素數 N 的 (N-1) 的所有素數因子。然後使用 (N-1) / 素數因子計算所有冪。然後檢查素數冪模 n 的值。如果它永遠不為 1，則 i 是原根。我們看到的第一個值將作為返回值，因為一個數字可能有多個原根，但我們只需要最小的一個。
示例
讓我們舉個例子來理解這個問題
#include<bits/stdc++.h>
using namespace std;
int calcPowerMod(int x, unsigned int y, int p){
int modVal = 1;
x = x % p;
while (y > 0){
if (y & 1)
modVal = (modVal*x) % p;
y = y >> 1;
x = (x*x) % p;
}
return modVal;
}
void findAllPrimeFactors(unordered_set<int> &s, int n){
while (n%2 == 0){
s.insert(2);
n = n/2;
}
for (int i = 3; i*i <= n; i = i+2){
while (n%i == 0){
s.insert(i);
n = n/i;
}
}
if (n > 2)
s.insert(n);
}
int findSmallestPrimitiveRoot(int n){
unordered_set<int> primes;
int phi = n-1;
findAllPrimeFactors(primes, phi);
for (int r=2; r<=phi; r++){
bool flag = false;
for (auto it = primes.begin(); it != primes.end(); it++){
if (calcPowerMod(r, phi/(*it), n) == 1){
flag = true;
break;
}
}
if (flag == false)
return r;
}
return -1;
}
int main(){
int n = 809;
cout<<"The smallest primitive root is "<<findSmallestPrimitiveRoot(n);
return 0;
}輸出
The smallest primitive root is 3
更新於： 2022年1月24日
584 次檢視
廣告