数学知识总结

求n的p次方，对M的取模
递归：

#define M 10003
 
int PowMod(int n, int p)
{
	if (p == 1)
	{
		return n % M;
	}
	int temp = Pow(n, p/2);
	int result = (temp*temp) % M;
	if (p % 2 == 1)
	{
		result = (result*n) % M;
	}
	return result;
}

非递归：

#define M 10003
 
int PowMod(int n, int p)
{
	int result = 1;
	while (p > 0)
	{
		if (p % 2 == 1)
		{
			result = (result*n) % M;
		}
		p /= 2;
		n = (n*n) % M;
	}
	return result;
}

n个数的拼凑，可以对d整除
gcd(a1​,a2​,a3​,⋯,an​)∣d⇔a1​x1​＋a2​x2​＋a3​x3​＋⋯＋an​xn​＝d
a1到an这n个数，都是无限个，他们的（倍数）加减拼凑，若是能拼出来一个d。
那么这n个数字的最大公因数一定可以被d整除