大数乘法的逆元

暴力法：

1  int i;
2     for (i=1;;i++) { if (((long long int)(n)*i-an)%M==0) break; }

欧拉函数

1 long long inv( long long n )
2 {
3     return pow( n, M - 2 )%M;
4 }

扩展欧几里得

 1 //扩展欧几里德
 2 void exp_gcd( LL a ,LL b,LL &x,LL &y) {
 3      if( b == 0 ) {
 4          x = 1;
 5          y = 0;
 6      }
 7      else {
 8           exp_gcd( b,a%b,x,y );
 9           LL t;
10           t = x;
11           x = y;
12           y = t - a/b*y;
13      }
14 }
15 //逆元
16 inline LL getNN(LL x) {
17         LL now , t;
18         exp_gcd( x, M,now,t );
19         return (now%M+M)%M;
20 }

还有一个

1 int64 inv(int64 x) {  
2     if(x == 1) return 1;  
3     return  inv(M%x) * (M - M/x) % M;  
4 }

1 void Inv( )
2 {    
3     inv[1]=1;
4     for(int i=2;i<=n;i++){
5         inv[i]=M-(M/i)*inv[M%i]%M;
6 }