标签：约数 gcd 数论 质数 基础 int quad Rightarrow

目录

• 质数
  • 质因数分解
• 约数
  • \(gcd\)求最大公约数

质数

质因数分解

算术基本定理：
\(任何一个大于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:\quad d是a的约数\)
\(2. 除法定理：对于任何整数a和任何整数，存在唯一整数r和q，满足0<=r<n\)
\(\quad \quad \quad \quad \quad a=qn+r\)
\(\quad \quad \quad \quad \quad q为商q=\lceil \dfrac an \rceil \qquad r为余数，r=a \quad mod \quad n\)
\(\quad \quad \quad \quad \quad n|a当且仅当r=a \quad mod \quad n=0\)
\(3. d|a并且d|y\Rightarrow 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) \Rightarrow q|a且q|b \Rightarrow q|(ax+by)\)
\(a\%b=a-kb \Rightarrow gcd(b,a\%b)=gcd(b,a-kb) \Rightarrow q|gcd(b,a\%b)\)
\(gcd(a,b)|gcd(b,a\%b)得证\)
\(下面只需要证明gcd(b,a\%b)|gcd(a,b)即可\)
\(p|(xb+y(a-kb)) \Rightarrow p|(ay+(x-k)b) \Rightarrow p|a并且p|b\)
\(p|a并且p|b \Rightarrow p|gcd(a,b) \Rightarrow 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;
}

未完待续......

标签：约数,gcd,数论,质数,基础,int,quad,Rightarrow
From： https://www.cnblogs.com/cxy8/p/17921355.html