同余与取模

同余与模运算

三个公式：

 

输入正整数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; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}