拓展欧里几得算法和费马小定理算法详解 大组合数求模
扩展欧几里德算法
是用来在已知 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
示意图
快速求幂取模
刷题中让直接求幂的不多，求幂后取模的却不少，毕竟求幂结果太大了。
水平所限，只会用二分幂取模，时间复杂度与二分幂一样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;
}
加油，我做的再也不是加减乘除。