基础数论1

质数

质因数分解

算术基本定理：
$任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可以写作：$
$$N=p_1^{c_1}{p}_2^{c_2}...p_m^{c_m}$$
$其中c_i都是正整数，p_i都是质数，且满足p_1<p_2<...<p_m$

int primes[N], cnt[N], m;
void divide(int n)
{
	rep(i,2,n/i)
	{
		if(n%i==0)	primes[++m]=i;
		while(n%i==0)
		{
			n/=i;
			cnt[m]++;
		}
	}
	if(n>1)	
	{
		primes[++m]=n;
		cnt[m]=1;
	}
}

哪个if是不是多余？
并不是的之前我感觉那个if是多余的，直接用map去存可以省掉哪个if但是用map去存复杂度就变成了$O(logn)$

约数

$gcd$求最大公约数

$gcd求最大公约数主要用到一个定理$
$$gcd(a,b)=gcd(b,a\%b)$$
下面证明该定理：
首先需要引入一些数论中用于证明的基本知识：
$1.d|a且d>=0:d是a的约数$
$2.除法定理：对于任何整数a和任何整数，存在唯一整数r和q，满足0<=r<n$
$a=qn+r$
$q为商q=?\frac{a}{n}?r为余数，r=amodn$
$n|a当且仅当r=amodn=0$
$3.d|a并且d|y?d|(ax+by)并且d|gcd(a,b)，因为gcd(a,b)是最大的约数$
证明：
如果能证明$gcd(a,b)|gcd(b,a\%b)并且gcd(b,a\%b)|gcd(a,b)$
$那么gcd(a,b)=gcd(b,a\%b)$
$令q=gcd(a,b),p=gcd(b,a\%b)$
$q=gcd(a,b)?q|a且q|b?q|(ax+by)$
$a\%b=a?kb?gcd(b,a\%b)=gcd(b,a?kb)?q|gcd(b,a\%b)$
$gcd(a,b)|gcd(b,a\%b)得证$
$下面只需要证明gcd(b,a\%b)|gcd(a,b)即可$
$p|(xb+y(a?kb))?p|(ay+(x?k)b)?p|a并且p|b$
$p|a并且p|b?p|gcd(a,b)?gcd(b,a\%b)|gcd(a,b)$
$$至此gcd(a,b)=gcd(b,a\%b)得证$$

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

未完待续…