資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 中的費馬小定理
費馬小定理 −
此定理指出，對於任何質數 p，
Ap - p 是 p 的倍數。
此陳述在模運算中表示為：
ap ≡ a (mod p)
如果 a 不能被 p 整除，則
ap - 1 ≡ 1 (mod p)
在這個問題中，給出了兩個數字 a 和 p。我們的任務是驗證這些值上的費馬小定理。
我們需要檢查ap ≡ a (mod p)，或ap - 1 ≡ 1 (mod p)
對於給定的 a 和 p 值成立。
來舉個例子來理解這個問題，
輸入： a = 3，p = 7
輸出： True
解釋：
Ap-1 ≡ 1 (mod p)
=> 36 ≡ 729
=> 729 - 1 = 728
=> 728 / 7 = 104
說明此定理的工作原理的程式，
範例
#include <iostream>
#include <math.h>
using namespace std;
int fermatLittle(int a, int p) {
int powVal;
if(a % p == 0){
powVal = pow(a, p);
if((powVal - p) % p == 0){
cout<<"Fermat's little theorem holds true!";
}
else{
cout<<"Fermat's little theorem holds false!";
}
}
else {
powVal = pow(a, (p - 1));
if((powVal - 1) % p == 0 ){
cout<<"Fermat's little theorem holds true!";
}
else{
cout<<"Fermat's little theorem holds false!";
}
}
}
int main()
{
int a = 3, m = 11;
fermatLittle(a, m);
return 0;
}輸出 −
Fermat's little theorem holds true!
更新於： 22-01-2021
671 次瀏覽量
廣告