高次方求模

2019-04-13 13:13发布

站内文章 / 模拟电子
18099 0 1775
有了这个公式，求解问题就简单了，n的p次方很容易拆分为几个数相乘的形式。其中采用二分法拆分较为简单高效。
递归： #define M 10003 int PowMod(int n, int p) { if (p == 1) { return n % M; } int temp = Pow(n, p/2); int result = (temp*temp) % M; if (p % 2 == 1) { result = (result*n) % M; } return result; } 非递归： #define M 10003 int PowMod(int n, int p) { int result = 1; while (p > 0) { if (p % 2 == 1) { result = (result*n) % M; } p /= 2; n = (n*n) % M; } return result; }

热门文章