基础数论1

数学是编程中永远绕不开的一个点，而在一些算法竞赛（蓝桥杯、NOIP等）中，数学问题还出现的蛮多的，这篇文章谈一谈如下几个点：

整除及取余
最大公约数与最小公倍数
质数与筛法

整除：

约数与倍数：a|b，a为b的约数，b是a的倍数，称a为b的因子，有个小结论：任何数n至少有两个因子，1和n本身，将他们称为n的平凡因子（平凡意味着很普遍嘛）

有个小问题可以思考一下：

求[1,n]中每个数的约数个数，n的每个约数d(n)，给出一个O(nlogn)的算法：
（思考一下再往下看？）

这个地方我们可以转换成倍数来搞，暴力枚举：将1到n中1的倍数全部标记一遍、再将1到n中2的倍数全部标记一遍，最后看每个数标记了多少次就知道有多少个约数啦。

复杂度分析：用1标记时，每个数都要标记，O(n)的复杂度；用2标记时，一半的数要标记，O(n/2)的复杂度......
最终的复杂度就是n+n/2+n/3+...=n(1+1/2+1/3...) 后面的括号里面的内容称为调和级数，求和为logn，所以时间复杂度就是O(nlogn)了。

想一想代码怎么写？

#include<iostream>
using namespace std;

int main()
{
	int a[105] = {0};
	int n = 100;
	for(int i = 1 ; i <= n ; ++i)   //打标记
	{
		for(int j = 1 ; j * i <= n ; ++j)
			a[i*j]++;
	}
	
	for(int i = 1 ; i <= 10 ; ++i)   //输出每个数被标记了多少次
	{
		cout<<"a["<<i<<"]"<<" = "<<a[i]<<endl;
	}
	return 0;
 }

质数：

质数：质数是不存在非平凡因子的个数，如果一个数的因子要出现，肯定是成对吹出现的，这个应该不需要证明，例如，n = a * b，一个肯定小于等于sqrt(n)，一个大于等于sqrt(n)，所有如果要枚举判断质数，只需要O(sqrt(n))的算就可以判断质数。

1既不是质数也不是合数，这个关系到整个数论这个体系成不成立，是公认的，不做证明。。。

质数有无限个，如何证明？（可以先别往下滑，思考一下，这个证明太厉害了）

我开始了...
首先要用到反证法：假设质数有限
假设有一个M，M=p1*p2*...*pn + 1 (p在这里是质数，且有限，最多是pn)，那么M%p1 == 1 , M%p2 == 1，继续往下M%pn == 1，这个就可以直接推出M是质数了，M比p中所有的数都要大（显然），与假设矛盾，所以质数无限

求质数：朴素办法是用循环枚举，复杂度为O(n*sqrt(n))
筛法：先筛掉2的倍数，再筛掉3的倍数，直到n的倍数，最后留下来的数就是质数了，像想一想代码怎么写：

#include<iostream>
using namespace std;

int main()
{
	int a[105] = {0} , n = 100;
	for(int i = 2 ; i <= n ; ++i)
	{
		if(a[i] == 0)
		{

		    cout<<i<<" ";
		    for(int j = 2 ; i*j <= n ; ++j)  //筛选
			a[i*j] = 1;
		}
	}
	return 0;
 }

质因数分解：

质因数分解：每个数都可以拆成质数乘积的方式，这个过程叫做质因数分解
eg. 5 = 5 = pow(5,1) //表示5的一次方
15 = 3 * 5 = pow(3,1) * pow(5,1)
36 = 2*2*3*3 = pow(2,2) * pow(3,2)

有一个思考题：给定一个质因数的分解形式，如何求d(n) （不记得d(n)是啥的往上翻）。这个题可以在评论区留言讨论，，好吧，估计也没人看。

模：

除法表示：a = 1/p * p + a%p (1/p是C语言中的表示，因为下取整的那个符号我不会打..)

模的性质：a%p一定落在[0,p-1]之间（显然）
随时取模性质：在只含加法和乘法的式子中，如果左后的运算结果需要对p取模，则可以在运算过程中随便取模，只需最后把结果再对p取模，答案就是正确的

随时取模性质可以防止在计算过程中爆int，爆long int。

大名鼎鼎的GCD与LCM

gcd(a,b)=d , a,b的最大公因数 条件：d|a , d|b && d要最大
lcm(a,b) = d , a,b的最小公倍数

eg. gcd(40,60) = 20 gcd(30,80) = 10
gcd(33,7) = 1 if(gcd(a,p) = 1) , 则a和p互质

有个思考问题：把A分解成了pow(2,a1)*pow(3,a2)*pow(5,a3)
把B分解成了pow(2,b1)*pow(3,b2)*pow(5,b3)
快速求d = gcd(A,B)，仅作思考，不要求，因为求gcd一般都用辗转相除

GCD递归定理，gcd(a,b) = gcd(b,a%b)，在求gcd时，用递归比用循环迭代好看很多

#include<iostream>
using namespace std;

int gcd(int a , int b)
{
	if(b == 0)
		return a;
	return gcd(b , a%b);
}

int main()
{
	int a = 7 , b = 28;
	cout<<gcd(a,b)<<endl;
	return 0;
 }

最后一点，再计算lcm时，lcm=a*b/gcd(a,b)，易爆int，可以改成lcm = a/gcd(a,b) * b