拓展欧里几得算法和费马小定理算法详解大组合数求模

Myth丶恋晨 2024-02-18 22:19 9阅读 0赞

**扩展欧几里德算法**

是用来在已知 a , b 求解一组 x , y ，使它们满足贝祖等式：ax+by=gcd( a , b ) （解一定存在，根据数论中相关定理）；常用在求解模线性方程及方程组中。

现在来看，知道了a和b的最大公约数gcd,一定有这样的x和y，使得 a\*x+b\*y=gcd,这是一个不定方程（其实是一种丢番图方程），有多解是一定的，但我们只要找到一组特殊解x0 和y0，那么可以用特解表示出整个的不定方程的通解：

**定理1：设a，b是整数且d=gcd（a，b）。如果c不能被d整除那么方程ax+by=c没有整数解。如果c能被d整除那么存在无穷多个整数解，另外，如果x=x0，y=y0是方程的一个特解，那么所有的解可以表示为：(线性丢番图方程)**

**x=x0 + ( b / d )\*t ;**

**y=y0 + ( a / d )\*t ;** **其中 t 为任意整数**

那么如何求出特解x0和y0呢，就是在欧几里得算法稍稍改动。

欧几里德算法的停止状态为：a=gcd , b=0; 那么在这个状态可知 a的系数是1，b因为是0，系数无所谓多少,在这让b的系数也为0了，此时 a\*1+b\*0=gcd ; 当然此时也是最终状态，那么我们也就可以根据这个最终状态倒推回去，倒退到a=a的原值，b=b的原值，那么此时 a , b的系数 x 和y不就是我们要求的特解x0和y0

**示意图**![70][]

**快速求幂取模**

刷题中让直接求幂的不多，求幂后取模的却不少，毕竟求幂结果太大了。  
水平所限，只会用二分幂取模，时间复杂度与二分幂一样O(lgn)。  
基本可以在各种比赛中顺利通过，也是目前比较常用的方法

原理同样很简单，都是小学学过的：积的取余等于取余的积取余 (涉及到同余定理)  
接下来用代码实现

int pow(int a,int n,int b)//返回值是a的n次方对b取余后的值

int result=1;

a=a%b;//积的取余等于取余的积取余

while(n>0)

if(n%2==1)

result=result\*a%b;//n是奇数的话就要多乘一次，原理和前面的二分求幂一样

n=n/2;//二分

a=a\*a%b;//积的取余等于取余的积取余

return result;

\#include<iostream>  
\#include<cmath>  
using namespace std;  
\#define LL long long  
\#define N 1000000  
\#define mod 100003  
int a\[N+9\]=\{1,1\};  
void MT()  
\{  
for(int i=2;i<=N;i++)  
a\[i\]=a\[i-1\]\*i%mod;  
\}  
LL KT(LL a,LL b,LL &x,LL &y)  
\{  
if(b==0)  
\{  
x=1;  
y=0;  
return a;  
\}  
else  
\{  
LL ans=KT(b,a%b,x,y);  
LL f=x;  
x=y;  
y=f-a/b\*y;  
return ans;  
\}  
\}  
//\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
LL KTT(LL a,LL b) //欧里几得算法求逆元 没有范围  
\{  
LL x,y;  
LL sum=KT(a,b,x,y);  
if(sum!=1)  
return -1;  
else  
if(sum==1)  
return ((x%mod)+mod)%mod;  
  
\}  
LL D(LL n,LL k)  
\{  
if(k<0)  
return 0;  
else  
return a\[n\]\*(KTT(a\[k\]\*a\[n-k\],mod))%mod;  
\}  
LL Lucas(LL n,LL k)  
\{  
if(k==0)  
return 1;  
else  
return D(n%mod,k%mod)\*Lucas(n/mod,k/mod)%mod;  
\}  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
LL quick\_mod(LL n,LL k) //费马小定理求逆元 mod只能是素数  
\{  
LL sum=1;  
n%=mod;  
while(k!=0)  
\{  
if(k&1)  
sum=sum\*n%mod; //这个地方不能写成sum\*=。。。。，这样出不来结果。  
n=n\*n%mod;  
k>>=1;  
\}  
return sum;  
\}  
LL D(LL n,LL k)  
\{  
if(k<0)  
return 0;  
else  
return a\[n\]\*(quick\_mod(a\[n-k\]\*a\[k\]%mod,mod-2))%mod;  
\}  
LL Lucas(LL n,LL k) // 卢卡斯算法  
\{  
if(k==0)  
return 1;  
else  
return D(n%mod,k%mod)\*Lucas(n/mod,k/mod)%mod;  
\}  
//\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

int main()  
\{  
int n;  
MT();  
cin>>n;  
while(n--)  
\{  
long long int m,r;  
cin>>m>>r;  
printf("%lld\\n",Lucas(m,r));  
\}  
return 0;  
\}

加油，我做的再也不是加减乘除。

[70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/d3b4092014d546de9d0656027dd6ae99.png