快速幂 & 大数取模及例题(极其详细) |
您所在的位置：网站首页 › 幂次方计算在线 › 快速幂 & 大数取模及例题(极其详细) |
|
首先，以杭电OJ的一道题引入话题 人见人爱A ^ B 接着，先给出取模的几个重要结论： (a * b) % p = (a % p * b) % p(a + b) % p = (a % p + b) % p(a + b) % p = (a % p + b % p) % p(a - b）% p = (a % p - b % p) % p(a * b）% p = (a % p * b % p) % p对于最后一条性质，即多个因子连续的乘积取模的结果等于每个因子取模后的乘积再取模的结果 上题的要求也简洁明了。即A的B次方结果的最后三位数所表示的整数。之所以把所表示的整数加粗，是由于要考虑到最后三位数字的首位为0的情况，如最后三位是024，那么程序输出的整数应该为24。 很多人看到这道题，第一反应是这还不简单，直接一个pow函数求出A的B次方，再对结果取最后三位数字不久好了？下面附上代码 #include #include #include using namespace std; int main() { int a,b; //a表示底数,b表示指数 cin >> a >> b; int p = pow(a,b); //pow(a,b)可以求出a的b次方 cout res = res * base; } long long ans = res % 1000; cout if (base == 0 && power == 0) break; long long res = 1; //执行power次循环,每次结果都乘一个base,即base的power次方 for (long long i = 1;i long long ans = 1; while(n) { if (n % 2) ans *= a;//指数为奇数 a = a * a;//底数平方 n /= 2;//指数减半 } return ans; }读者可以根据以上代码计算一下2的16次方加深板子的理解和记忆，当然也可将数据类型改为int 那么，当快速幂和大数取模相结合，就可以求出超过long long范围的数(long long 最大是2的63次方)的最后几位 例如： 以下代码可以快速求出2的1000000000次方的最后三位数字 #include using namespace std; //快速幂与大数取模结合 long long quick_power(long long a,long long n) { long long ans = 1; while(n) { if (n % 2) ans = ans * a % 1000;//奇数 a = a * a % 1000;//底数平方的最后3位数字 n /= 2;//指数减半 } return ans; } int main() { cout if (n & 1) ans = ans * a % 1000;//奇数 a = a * a % 1000; n >>= 1;//n >> 1可将原数减半,n >>= 1等价于n = n / 2 } return ans; } int main() { cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |