算法竞赛入门经典第十章学习笔记 大整数取模 幂取模

10-1 大整数取模
题目：输入整整数n和m，输出n mod m的值。$n\le 10^{100},m\le 10^9$。
这道题的特别之处在于n的范围很大，无法用整型变量保存和直接计算。大整数n用两个字符串保存，m可以用整型保存。我们可以将n的每位数字分离，变成如下形式：$abcde=((((a\times 10+b)\times 10+c)\times 10+d)\times 10+e)$，每步取模。

#include<iostream>
#include<math.h>
#include<string>
using namespace std;
long long int big_num_mod(string a, long long int b)
{
long long int ans=0;
for(int i=0;i<a.length();i++)
ans=(ans*10+a[i]-48)%b;
return ans;
}
int main()
{
string n;
long long int m;
cin>>n>>m;
long long int ans=big_num_mod(n,m);
cout<<endl<<"Answer is: "<<ans;
}

10-2 幂取模
输入正整数a, n和m, 输出$a^n$ $mod$ $m$的值。
如果直接计算pow(a,n)%m，pow(a，n)可能溢出。可以循环n次每次取模：

int ans=a%m;
for(int i=1;i<n;i++)
ans=ans*a%m;
return ans;

不太可能溢出，但是时间为O(n)，当n比较大时，需要一个更快的算法。我们注意到$a^n=(a^2{)}^{n/2}$，只需要将n扩大一倍，n次乘法会变成n/2次乘法。继续二分下去有可能使O(n)的时间变为O(logn)的时间。但是需要注意当n为奇数时，$a^n=(a^2{)}^{n/2}\times a$，因为n/2向下取整会少作一次乘法。递归算法：

#include<iostream>
using namespace std;
long long int power_mod(int a, int n, int m)
{
if(!n) return 1;
if(n & 1) return a*power_mod(a*a, n/2, m)%m;
return power_mod(a*a, n/2, m);
}
int main()
{
int a, n, m;
cout<<"a: n: m: "<<endl;
cin>>a>>n>>m;
long long int ans = power_mod(a, n, m);
cout<<endl<<"Answer is: "<<ans;
}

非递归算法（while循环）：

#include<iostream>
using namespace std;
long long int power_mod(int a, int n, int m)
{
int ans=1;
while(n>0)
{
if(n & 1) ans=ans*a%m;
a=a*a%m;
n/=2;
}
return ans;
}
int main()
{
int a, n, m;
cout<<"a: n: m: "<<endl;
cin>>a>>n>>m;
long long int ans = power_mod(a, n, m);
cout<<endl<<"Answer is: "<<ans;
}

最后

以上就是阔达唇彩为你收集整理的算法竞赛入门经典第十章学习笔记 大整数取模 幂取模的全部内容，希望文章能够帮你解决算法竞赛入门经典第十章学习笔记 大整数取模 幂取模所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。