同余与取模

同余与模运算

三个公式：

 

输入正整数n和m。输出n mod m的值，n<=10^100,m<=10^9.

 

输入正整数a，n，m，输出a^n mod m的值，a，n，m<=10^9.

 

#include <iostream>
using namespace std;
int pow(int a,int n,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 = ans * a % m;
return ans;
}
int main()
{
cout<<pow(2,3,6)<<endl;
cout<<pow_mod(2,3,6)<<endl;
return 0;
}