基础数论1

2023-12-22 13:49:38

质数

质因数分解

算术基本定理:
任何一个大于 1 的正整数都能唯一分解为有限个质数的乘积,可以写作: 任何一个大于1的正整数都能唯一分解为有限个质数的乘积,可以写作: 任何一个大于1的正整数都能唯一分解为有限个质数的乘积,可以写作:
N = p 1 c 1 p 2 c 2 . . . p m c m N=p_1^{c_1}p_2^{c_2}...p_m^{c_m} N=p1c1??p2c2??...pmcm??
其中 c i 都是正整数, p i 都是质数,且满足 p 1 < p 2 < . . . < p m 其中c_i都是正整数,p_i都是质数,且满足p_1<p_2<...<p_m 其中ci?都是正整数,pi?都是质数,且满足p1?<p2?<...<pm?

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 ( l o g n ) O(logn) O(logn)

约数

g c d gcd gcd求最大公约数

g c d 求最大公约数主要用到一个定理 gcd求最大公约数主要用到一个定理 gcd求最大公约数主要用到一个定理
g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a\%b) gcd(a,b)=gcd(b,a%b)
下面证明该定理:
首先需要引入一些数论中用于证明的基本知识:
1. d ∣ a 且 d > = 0 : d 是 a 的约数 1. d|a且d>=0:\quad d是a的约数 1.dad>=0:da的约数
2. 除法定理:对于任何整数 a 和任何整数,存在唯一整数 r 和 q ,满足 0 < = r < n 2. 除法定理:对于任何整数a和任何整数,存在唯一整数r和q,满足0<=r<n 2.除法定理:对于任何整数a和任何整数,存在唯一整数rq,满足0<=r<n
a = q n + r \quad \quad \quad \quad \quad a=qn+r a=qn+r
q 为商 q = ? a n ? r 为余数, r = a m o d n \quad \quad \quad \quad \quad q为商q=\lceil \dfrac an \rceil \qquad r为余数,r=a \quad mod \quad n q为商q=?na??r为余数,r=amodn
n ∣ a 当且仅当 r = a m o d n = 0 \quad \quad \quad \quad \quad n|a当且仅当r=a \quad mod \quad n=0 na当且仅当r=amodn=0
3. d ∣ a 并且 d ∣ y ? d ∣ ( a x + b y ) 并且 d ∣ g c d ( a , b ) ,因为 g c d ( a , b ) 是最大的约数 3. d|a并且d|y\Rightarrow d|(ax+by)并且d|gcd(a,b),因为gcd(a,b)是最大的约数 3.da并且dy?d(ax+by)并且dgcd(a,b),因为gcd(a,b)是最大的约数
证明:
如果能证明 g c d ( a , b ) ∣ g c d ( b , a % b ) 并且 g c d ( b , a % b ) ∣ g c d ( a , b ) gcd(a,b)|gcd(b,a\%b)并且gcd(b,a\%b)|gcd(a,b) gcd(a,b)gcd(b,a%b)并且gcd(b,a%b)gcd(a,b)
那么 g c d ( a , b ) = g c d ( b , a % b ) 那么gcd(a,b)=gcd(b,a\%b) 那么gcd(a,b)=gcd(b,a%b)
令 q = g c d ( a , b ) , p = g c d ( b , a % b ) 令q=gcd(a,b), p=gcd(b,a\%b) q=gcd(a,b),p=gcd(b,a%b)
q = g c d ( a , b ) ? q ∣ a 且 q ∣ b ? q ∣ ( a x + b y ) q=gcd(a,b) \Rightarrow q|a且q|b \Rightarrow q|(ax+by) q=gcd(a,b)?qaqb?q(ax+by)
a % b = a ? k b ? g c d ( b , a % b ) = g c d ( b , a ? k b ) ? q ∣ g c d ( b , a % b ) a\%b=a-kb \Rightarrow gcd(b,a\%b)=gcd(b,a-kb) \Rightarrow q|gcd(b,a\%b) a%b=a?kb?gcd(b,a%b)=gcd(b,a?kb)?qgcd(b,a%b)
g c d ( a , b ) ∣ g c d ( b , a % b ) 得证 gcd(a,b)|gcd(b,a\%b)得证 gcd(a,b)gcd(b,a%b)得证
下面只需要证明 g c d ( b , a % b ) ∣ g c d ( a , b ) 即可 下面只需要证明gcd(b,a\%b)|gcd(a,b)即可 下面只需要证明gcd(b,a%b)gcd(a,b)即可
p ∣ ( x b + y ( a ? k b ) ) ? p ∣ ( a y + ( x ? k ) b ) ? p ∣ a 并且 p ∣ b p|(xb+y(a-kb)) \Rightarrow p|(ay+(x-k)b) \Rightarrow p|a并且p|b p(xb+y(a?kb))?p(ay+(x?k)b)?pa并且pb
p ∣ a 并且 p ∣ b ? p ∣ g c d ( a , b ) ? g c d ( b , a % b ) ∣ g c d ( a , b ) p|a并且p|b \Rightarrow p|gcd(a,b) \Rightarrow gcd(b,a\%b)|gcd(a,b) pa并且pb?pgcd(a,b)?gcd(b,a%b)gcd(a,b)
至此 g c d ( a , b ) = g c d ( b , a % b ) 得证 至此gcd(a,b)=gcd(b,a\%b) 得证 至此gcd(a,b)=gcd(b,a%b)得证

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

未完待续…

文章来源:https://blog.csdn.net/weixin_61426225/article/details/135150686
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。