[C++知识库]一点数论知识

(a+b)%n ＝ (a%n+b%n)%n

(a * b)%n＝((a%n) * (a%n))%n

lcm:最小公倍数
gcd:最大公倍数

lcm(a,b)=a * b/gcd(a,b)

求最大公约数函数:

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}

c++的algorithm库函数内置好了最大公约数模板 加一个头文件 #include < algorithm >直接调用__gcd(a,b),返回值就是a和b的最大公约数,注意：gcd前面有两道下划线

关于怎么判断一个数n是否是质数，最简单的方法是枚举2到n-1，判断是否是n的约数。如果是，n肯定不是一个质数。再仔细想想，如果a是n的一个约数，那么必然有一个b满足ab=n，a <= 根号n 和 b <= 根号n 中必然有一个成立，因为如果a>根号n并且b>根号n，那么ab>n,和ab=n矛盾。因此如果n是一个合数，那么我们只需要枚举到根号n就一定能找到n的一个约数。否则，n肯定是一个质数。

bool is_prime(int n)
{
	if(n==1)
	{
		return false;//不是质数
	}
	for(inr i=2;i*i<=n;i++)
	{
		if(n%i==0)
		return false;//不是质数
	}
	return true;//是质数
}

质数筛算法：

#include <iostream>
using namespace std;
bool is_prime[100];
int main()
{
	for(int =2;i<100;i++)
	{
		is_prime[i]=true;
	}
	for(int i=2;i*i<100;i++）
	{
	if(is_prime[i])
	{
		for(int j=i*i;j<100;j+=i)
		{
			is_prime[j]=false;
		}
	}
	}
	for(inr i=2;i<100;i++)
	{
		if(is_prime[i]
		{
			cout<,i<<endl;
		}
	}
}

另：欧拉函数 和 快速幂 和 矩阵乘法知识