质数
质因数分解
算术基本定理：
\(任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可以写作：\)
\(其中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求最大公约数主要用到一个定理\)
下面证明该定理：
首先需要引入一些数论中用于证明的基本知识：
\(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)\)
int gcd(int a, int b)
{
return b?gcd(b,a%b):a;
}
未完待续......