给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入输出格式输入格式：
一行n,p
输出格式：
n行,第i行表示i在模p意义下的逆元。
输入输出样例
输入样例#1：
10 13
输出样例#1：
179108112534
说明
1≤n≤3×106,n<p<20000528
输入保证p为质数。
Solution：首先我们来了解一下逆元。
若a*x≡1(mod b)，a、b互质，则称x为a的逆元，记为a-1。根据逆元的定义，可转化为a*x+b*y=1，用扩展欧几里德法求解。逆元可以用来在计算(t/a)mod b时，转化为t*a-1mod b。
利用快速幂及扩展欧几里德算法求逆元代码如下：
1 void exgcd(int a,int b,int &x,int &y){ 2 if(a==0){x=0;y=1;return;} 3 else { 4 int tx,ty; 5 exgcd(b%a,a,tx,ty); 6 x=ty-(b/a)*tx; 7 y=tx; 8 return; 9 }10 }
求逆元还有一个线性算法，具体过程如下。
首先，1-1≡1(mod p)。
然后，我们设p=k*i+r，r<i,1<i<p，再将这个式子放到mod p意义下就会得到：k*i+r≡0(mod p)
再两边同时乘上i-1、r-1就会得到：
k*r-1+i-1≡0(mod p) --> i-1≡-k*r-1(mod p) --> i-1≡-[p/i]*(p mod i)-1 (mod p)
于是，就可以从前面推出当前的逆元。代码也就一行：a[i]=-(p/i)*a[p%i];
然后这道模板题，便是用上述方法解决的。。
1 #include 2 using namespace std; 3 #define ll long long 4 #define il inline 5 #define inf 233333333333 6 ll n,p,a[3000600],b; 7 int main() 8 { 9 scanf("%lld%lld",&n,&p);10 a[1]=1;11 for(int i=2;i<=n;i++){12 a[i]=-(p/i)*a[p%i];13 while(a[i]<0)a[i]+=p;14 printf("%lld\n",a[i-1]);15 }16 printf("%lld\n",a[n]);17 return 0;18 } 洛谷 P3807 【模板】卢卡斯定理题目描述
给定n,m,p(1≤n,m,p≤1051\le n,m,p\le 10^51≤n,m,p≤105)
求 Cn+mm mod pC_{n+m}^{m}\ mod\ pCn+mm mod p
保证P为prime
C表示组合数。
一个测试点内包含多组数据。
输入输出格式
输入格式：
第一行一个整数T(T≤10T\le 10T≤10)，表示数据组数
第二行开始共T行，每行三个数n m p，意义如上
输出格式：
共T行，每行一个整数表示答案。
输入输出样例
输入样例#1： 复制
21 2 52 1 5
输出样例#1： 复制
3 3
Solution：Lucas定理。
就是C(n,m) mod p=C(n%p,m%p)*C(n/p,m/p)%p。
证明：不会。记着就行。(×)
代码实现方面，注意两点：
1.对于C(n/p,m/p)部分可以继续使用Lucas定理递归求解。
2.求逆元，可以用费马小定理做快速幂，当然也可以线性预处理阶乘逆元。注意，若线性预处理，需要将000位赋位111（很好理解，不做解释）。
代码： 1 #include 2 using namespace std; 3 #define ll long long 4 #define il inline 5 ll n,m,p,a[100005],b[100005]; 6 il ll gi() 7 { 8 ll a=0;char x=getchar();bool f=0; 9 while((x<'0'||x>'9')&&x!='-')x=getchar();10 if(x=='-')x=getchar(),f=1;11 while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();12 return f?-a:a;13 }14 il ll fast(ll n,ll m,ll p)15 {16 if(m>n)return 0;17 return a[n]*b[n-m]%p*b[m]%p;18 }19 il ll lucas(ll n, ll m ,ll p)20 {21 if(!m)return 1;22 return fast(n%p,m%p,p)*lucas(n/p,m/p,p)%p;23 }24 int main()25 {26 int t=gi();27 while(t--)28 {29 a[0]=b[0]=a[1]=b[1]=1;30 n=gi(),m=gi(),p=gi();31 n+=m;32 for(int i=2;i<=p;i++)b[i]=-(p/i)*b[p%i]%p;33 for(int i=2;i<=p;i++)a[i]=a[i-1]*i%p,b[i]=b[i-1]*b[i]%p;34 printf("%lld\n",(lucas(n,m,p)+p)%p);35 }36 return 0;37 } 洛谷 P1082 同余方程题目描述求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
输入输出格式输入格式：
输入只有一行，包含两个正整数 a, b，用一个空格隔开。
输出格式：
输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。
输入输出样例输入样例#1：
3 10
输出样例#1：
7说明
【数据范围】
对于 40%的数据，2 ≤b≤ 1,000；
对于 60%的数据，2 ≤b≤ 50,000,000；
对于 100%的数据，2 ≤a, b≤ 2,000,000,000。
NOIP 2012 提高组 第二天 第一题
Solut����,����ion：求解线性同余方程，直接可以套上扩展欧几里德的模板。a*x≡c mod(b) 等同于 a*x+b*y=c ，有整数解的必要条件是：c%GCD(a,b)=0 。那么这道题就是在求a*x+b*y=1中x的最小解(特别的当a,b互质时，x为a的逆元)。扩欧我就不赘述了。
代码： 1 #include 2 using namespace std; 3 #define ll long long 4 #define il inline 5 il void exgcd(int a,int b,int &x,int &y) 6 { 7 if(!b){x=1,y=0;return;} 8 exgcd(b,a%b,x,y); 9 int t=x-a/b*y;10 x=y;y=t;11 return;12 }13 int a,b,x,y;14 int main()15 {16 scanf("%d%d",&a,&b);17 exgcd(a,b,x,y);18 while(x<0)x+=b;19 cout<<x;20 return 0;21 }