次方求模

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 using namesapace std;
 5 
 6 int main()
 7 {
 8       int a,b,c;
 9       cin>>a>>b>>c;
10       int ans;
11       ans=pow(a,b)%c;
12       return 0;      
13 }

简单的次方求模很简单,就像上文一样。

不过比较难的就是大数的次方求余。

对于a^b mod c .令N=a^b.

所以 N mod c =(N1 mod c * N2 mod c * N2 mod N3 * ~~~Nn mod c ) mod c .

有了这个式子,所以：

a^b=a^(b/2) * a^(b/2) .（采用二分法比较简单）

有两种代码的形式：

递归：

 1 //求a^b%c 
 2 
 3 int Powmod(int a,int b)//b为指数 
 4 {
 5     if(b == 1)
 6     {
 7         return a % c;
 8     }
 9     int temp;
10     temp = Powmod(a, b/2);//递归
11     int ans = (temp * temp) % c;
12     if(b % 2 == 1)//如果指数b并不能被2整除 
13     {
14         ans = (ans * a) % c;
15     }
16     return ans;
17 }

有时候递归会耗时，但也有用whlie循环的：

 1 int Powmod(int a,int b)
 2 {
 3     int ans = 1;
 4     while(b > 0)
 5     {
 6         if(b % 2 == 1)
 7         {
 8             ans = (ans * a) % c;
 9         }
10         p /= 2;
11         a = (a * a) % c;
12     }
13     return  ans;
14 }