a^b mod n
1
long long ModExp(long long a, long long b, long long n)
2
{
3
long long result=1, y=a;
4 while (b)
5
{
6 if (b%2 == 1)
7 result = result * y % n;
8 y = y * y % n;
9 b/=2;
10
}
11 return result;
12
}
13
求最大公约数，及其扩展
1 int Euclid(int a,int b)//a>=b,求a,b的最大公约数
2 {
3 if(b==0)
4 return a;
5 else
6 return Euclid(b,a%b);
7 }
8 int EuclidExtension(int a,int b,int &x,int &y)//a>=b ，求d=ax+by的x,y，其中d为两者的最大公约数
9 {
10
11 if(b==0)
12 {
13 x=1;
14 y=0;
15 return 1;
16 }
17 else
18 {
19 int x1,y1;
20 int d1=EuclidExtension(b,a%b,x1,y1);
21 x=y1;
22 y=x1-((int)(a/b))*y1;
23 return d1;
24 }
25 }