乘法相关

乘法逆元

 1 /***************************************
 2 函数：ExGcd 
 3 功能：求两个数的最大公约数和模P的乘法逆元。
 4 输入：a,b 输入参数，求这两个数的最大公约数
 5    和a模b的逆元 或 b模a的逆元。
 6 输出：x,y 分别表示a模b的逆元和b模a的逆元。
 7 返回：r 表示a b 的最大公约数。
 8 *************************************/
 9 int Exgcd(int a,int b,int &x,int  &y)
10 {
11     if(b==0){
12         x=1;
13         y=0;
14         return a;
15     }
16     int r=Exgcd(b,a%b,x,y);
17     int t=x;
18     x=y;
19     y=t-a/b*y;
20     return r;
21 }

View Code

a的n次方模N的O(lgn)算法

 1 /*
 2 
 3 a为底数，n为幂数，N为模数
 4 
 5 */
 6 
 7 int fac(int a,int n,int N)
 8 {
 9     a%=N;
10     int t=1;
11     while(n){
12         if(n%2) t=(t*a)%N; 
13         a=(a*a)%n;
14         n/=2;
15     }
16     return t;
17 }

View Code