免费建站推广,哈尔滨最新,短网址是什么,无忧ppt模板下载 免费文章目录 质数质因数分解 约数 g c d gcd gcd求最大公约数 质数
质因数分解
算术基本定理#xff1a; 任何一个大于 1 的正整数都能唯一分解为有限个质数的乘积#xff0c;可以写作#xff1a; 任何一个大于1的正整数都能唯一分解为有限个质数的乘积#xff0c;可以写作… 文章目录 质数质因数分解 约数 g c d gcd gcd求最大公约数 质数
质因数分解
算术基本定理 任何一个大于 1 的正整数都能唯一分解为有限个质数的乘积可以写作 任何一个大于1的正整数都能唯一分解为有限个质数的乘积可以写作 任何一个大于1的正整数都能唯一分解为有限个质数的乘积可以写作 N p 1 c 1 p 2 c 2 . . . p m c m Np_1^{c_1}p_2^{c_2}...p_m^{c_m} Np1c1p2c2...pmcm 其中 c i 都是正整数 p i 都是质数且满足 p 1 p 2 . . . p m 其中c_i都是正整数p_i都是质数且满足p_1p_2...p_m 其中ci都是正整数pi都是质数且满足p1p2...pm
int primes[N], cnt[N], m;
void divide(int n)
{rep(i,2,n/i){if(n%i0) primes[m]i;while(n%i0){n/i;cnt[m];}}if(n1) {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且d0:\quad d是a的约数 1.d∣a且d0:d是a的约数 2. 除法定理对于任何整数 a 和任何整数存在唯一整数 r 和 q 满足 0 r n 2. 除法定理对于任何整数a和任何整数存在唯一整数r和q满足0rn 2.除法定理对于任何整数a和任何整数存在唯一整数r和q满足0rn a q n r \quad \quad \quad \quad \quad aqnr aqnr q 为商 q ⌈ a n ⌉ r 为余数 r a m o d n \quad \quad \quad \quad \quad q为商q\lceil \dfrac an \rceil \qquad r为余数ra \quad mod \quad n q为商q⌈na⌉r为余数ramodn n ∣ a 当且仅当 r a m o d n 0 \quad \quad \quad \quad \quad n|a当且仅当ra \quad mod \quad n0 n∣a当且仅当ramodn0 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|(axby)并且d|gcd(a,b)因为gcd(a,b)是最大的约数 3.d∣a并且d∣y⇒d∣(axby)并且d∣gcd(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 ) 令qgcd(a,b), pgcd(b,a\%b) 令qgcd(a,b),pgcd(b,a%b) q g c d ( a , b ) ⇒ q ∣ a 且 q ∣ b ⇒ q ∣ ( a x b y ) qgcd(a,b) \Rightarrow q|a且q|b \Rightarrow q|(axby) qgcd(a,b)⇒q∣a且q∣b⇒q∣(axby) 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\%ba-kb \Rightarrow gcd(b,a\%b)gcd(b,a-kb) \Rightarrow q|gcd(b,a\%b) a%ba−kb⇒gcd(b,a%b)gcd(b,a−kb)⇒q∣gcd(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|(xby(a-kb)) \Rightarrow p|(ay(x-k)b) \Rightarrow p|a并且p|b p∣(xby(a−kb))⇒p∣(ay(x−k)b)⇒p∣a并且p∣b 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) p∣a并且p∣b⇒p∣gcd(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;
}未完待续…
