費馬小定理:
假如p是素數,且(a,p)=1,那麼a^(p-1)≡1(mod p)
ps:a≡b(modm)表示a,b對模m的餘數相同,如3三5(mod2)等
證明略
注意:
1、費馬小定理隻能在 gcd(a,p)=1 條件成立時使用
2、費馬定理是,已知素數p,得到
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CN1YzM5UzM1ADM4ITMwETMwIzLcFDMxEDMy8CXuV3cuVGbsF2Lc12bj91cn9Gbi52YvwVbvNmLzd2bsJmbj5ycldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
。但是已知
并不能确定p是素數。
3、 若
,則p一定為合數(費馬定理的逆反命題)。
費馬小定理在acm中的應用:
① 判斷素數,對于大素數的判定,Miller-Rabin 素數判定
②求解逆元 ,設a模p的逆元為x,則a*x≡1(mod p) ,(a,p)=1;由費馬小定理可以知道x=a^(p-2)
③對于計算a^b(modp) a^b(modp) 可簡化
對于素數p,任取跟他互素的數a,有a^(p-1)(mod p)=1
是以任取b,有a^b%p=a^(b%(p-1))(%p)進而簡化運算。
①、判斷素數模闆(利用(a^p-1)%p是否等于1 來判斷 是不是素數)
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <ctime>
#include <cmath>
using namespace std;
#define ll long long
//求a^p%mod
ll quick_pow(ll a,ll p,ll mod)
{
ll ans=1;
a=a%mod;
while(p)
{
if(p&1)
ans=ans*a%mod;
a=a*a%mod;
p>>=1;
}return ans;
}
/*
測試 n 是否為素數 s 為 測試次數 (一般為4次)
是素數 傳回 1 不是素數 傳回 0
*/
int Miller_Rabbin(ll n,int s)
{
ll a;
srand(time(NULL));
for(int i=1;i<=s;i++)
{
a=1+rand()%(n-1);
if(quick_pow(a,n-1,n)!=1)
return 0;
}return 1;
}
int main()
{
ll n;
while(cin>>n)//"n=1 的時候特判一下"
{
if(n==1) cout<<" 不是素數"<<endl;
else
if(Miller_Rabbin(n,4))
cout<<" 是素數"<<endl;
else cout<<" 不是素數"<<endl;
}return 0;
}
/*
1
不是素數
23
是素數
2
是素數
3
是素數
4
不是素數
5
是素數
6
不是素數
*/
②求解逆元
逆元類似導數的性質 (為什麼不是相等呢?搞不懂 (╥╯^╰╥) 迷之數論)
接下來引入求餘概念
(a + b) % p = (a%p + b%p) %p (對)
(a - b) % p = (a%p - b%p) %p (對)
(a * b) % p = (a%p * b%p) %p (對)
(a / b) % p = (a%p / b%p) %p (錯)--> 除法是不能直接取模的哦 反例:(100/50)%20 = 2 ≠ (100%20) / (50%20) %20 = 0
是以就要借助逆元了,來把除法轉化成乘法;
a的逆元,我們用inv(a)來表示
那麼-------------------->>>
(a / b) % p = (a * inv(b) ) % p = (a % p * inv(b) % p) % p ( p 是質數且 gcd(a, p) = 1,a才有關于p的逆元)
利用費馬小定理:a^(p-1)≡1(mod p) --> a^(p-2)≡1/a(mod p) --> a^(p-2)≡ inv(a) (mod p);
是以 : inv(a)= a^(p-2)(mod p) ;
利用快速幂求,
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <ctime>
#include <cmath>
using namespace std;
#define ll long long
ll quick_pow(ll a,ll b,ll mod)
{
ll ans=1;
while(b)
{
if(b&1)
ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
ll Fermat(ll a,ll p) //a 關于 p的逆元
{
return quick_pow(a,p-2,p);
}
int main()
{
ll a,p;
double ans=0;
cin>>a>>p;
ans=Fermat(a,p);
cout<<ans<<endl;
return 0;
}
③簡化計算。還是利用快速幂
快速幂不懂得 戳->https://mp.csdn.net/postedit/79393296