模的指数运算算法

2019-04-13 11:56发布

站内文章 / 模拟电子
13778 0 961
__int64 mod(__int64 a, __int64 b, __int64 n) { __int64 arr[500],z = -1,y; for( ; b != 1 ; b >>= 1)//分解b为二进制，记录下分解成的位数z构造栈arr { z++; if( b % 2 == 0) arr[z] = 0; else arr[z] = 1; } //a %= n如果一开始数很大，先模一次，防止过大，求逆 y = a * a % n;//第一次去模 for(; z > 0; z--) { if(arr[z]) y = (y*a%n) * (y*a%n); else y = y * y % n; } if( arr[0] ) y = (y*a % n);//最后一次取模 return y; }
幂取模 方法一： int pow_mod(int a,int b,int m) {      int ans = 1;      for(int i = 0; i < n; i++)           ans = (int )((long long) ans * n % m);      return ans; }   方法二：利用分治法使算法更快 int pow_mod(int a, int n,int m) { int x = pow_mod(a, n/2 ,m); long long ans = (long long)x * x % m; if(n%2 == 1 ) ans *= a%m; return int(ans); }
   

热门文章