算法-数学

最大公约数

欧几里得算法

写法一：递归写法

1
2
3
4
5
6
7
8
9
10
11

int gcd(int a, int b)

{

    if(b == 0) return a;

    return(b, a % b);

}

写法二：迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int gcd(int a, int b)

{

    while(b != 0)

    {

        int tmp = a;

        a = b;

        b = tmp % b;

    }

    return a;

}

快速幂

快速幂模板题: 洛谷P1226

1
2
3
4
5
6
7
8
9
10
11
int qmi(int a, int k, int p)
{
	int res = 1;
	while(k)
	{
		if(k & 1) (ll)res = res * a % p;
		k >>= 1;
		a = (ll)a * a % p;
	}
	return res;
}