网站用access做数据库吗,厦门seo推广外包,旅游网站开发,uc官方网站开发者中心0x32 约数
定义
若整数 n n n除以整数 d d d的余数为0#xff0c;即 d d d能整除 n n n#xff0c;则称 d d d是 n n n的约数#xff0c; n n n是 d d d的倍数#xff0c;记为 d ∣ n d|n d∣n。
算术基本定理的推论
在算术基本定理中#xff0c;若正整数 N N N被唯一…0x32 约数
定义
若整数 n n n除以整数 d d d的余数为0即 d d d能整除 n n n则称 d d d是 n n n的约数 n n n是 d d d的倍数记为 d ∣ n d|n d∣n。
算术基本定理的推论
在算术基本定理中若正整数 N N N被唯一分解为 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 c_i ci都是正整数 p i p_i pi都是质数且满足 p 1 p 2 . . . p m p_1p_2...p_m p1p2...pm则 N N N的正约数集合可写作 { p 1 b 1 p 2 b 2 . . . p m b m } , 其中 0 ≤ b i ≤ c i \{p_1^{b_1}p_2^{b_2}...p_m^{b_m} \},其中0\leq b_i \leq c_i {p1b1p2b2...pmbm},其中0≤bi≤ci N N N的正约数个数为 ( c 1 1 ) ∗ ( c 2 1 ) ∗ . . . ∗ ( c m 1 ) ∏ i 1 m ( c i 1 ) (c_11)*(c_21)*...*(c_m1)\prod_{i1}^m(c_i1) (c11)∗(c21)∗...∗(cm1)i1∏m(ci1) N N N的所有正约数的和为 ( 1 p 1 p 1 2 . . . p 1 c 1 ) ∗ . . . ∗ ( 1 p m p m 2 . . . p m c m ) ∏ i 1 m ( ∑ j 0 c i ( p i ) j ) (1p_1p_1^2...p_1^{c_1})*...*(1p_mp_m^2...p_m^{c_m})\prod_{i1}^m(\sum_{j0}^{c_i}{(p_i)}^j) (1p1p12...p1c1)∗...∗(1pmpm2...pmcm)i1∏m(j0∑ci(pi)j) 求 N N N的正约数集合——试除法
若 d ≥ N d\geq \sqrt{N} d≥N 是 N N N的约数则 N / d ≤ N N/d\leq \sqrt{N} N/d≤N 也是 N N N的约数。换言之约数总是成对出现的除了对于完全平方数 N \sqrt{N} N 会单独出现。
因此只需扫描 d 1 ∼ N d1\sim \sqrt{N} d1∼N 尝试 d d d能否整除 N N N若能整除则 N / d N/d N/d也是 N N N的约数。时间复杂度为 O ( N ) O(\sqrt{N}) O(N )。
int factor[1600],m0;
for(int i1;i*in;i)
{if(n%i0){factor[m]i;if(i!n/i) factor[m]n/i;}
}试除法的推论一个整数 N N N的约数个数上界为 2 N 2\sqrt{N} 2N 。
求 1 ∼ N 1\sim N 1∼N每个数的正约数集合——倍数法
若用“试除法”分别求出 1 ∼ N 1\sim N 1∼N每个数的正约数集合时间复杂度过高为 O ( N N ) O(N\sqrt{N} ) O(NN )。可以反过来考虑对于每个数 d d d 1 ∼ N 1\sim N 1∼N中以 d d d为约数的数就是 d d d的倍数 d , 2 d , 3 d , . . . , ⌊ N / d ⌋ ∗ d d,2d,3d,...,\lfloor N/d \rfloor *d d,2d,3d,...,⌊N/d⌋∗d。一下程序采用“倍数法”求出 1 ∼ N 1\sim N 1∼N每个数的正约数集合
vectorint factor[500010];
for(int i1;in/i;i)for(int j1;jn/i;j)factor[i*j].push_back(i);上述时间复杂度为 O ( N N / 2 N / 3 N / N ) O ( N l o g N ) O(NN/2N/3N/N)O(NlogN) O(NN/2N/3N/N)O(NlogN)。
倍数法的推论 1 ∼ N 1\sim N 1∼N每个数的约数个数的总和大约为 N l o g N NlogN NlogN。
1.最大公约数
定义
若自然数 d d d同时是自然数 a a a和 b b b的约数则称 d d d是 a a a和 b b b的公约数。在所有 a a a和 b b b的公约数中最大的一个称为 a a a和 b b b的最大公约数记为 g c d ( a , b ) gcd(a,b) gcd(a,b)。
若自然数 m m m同时是自然数 a a a和 b b b的倍数则称 m m m是 a a a和 b b b的公倍数。在所有 a a a和 b b b的公倍数中最小的一个称为 a a a和 b b b的最小公倍数记为 l c m ( a , b ) lcm(a,b) lcm(a,b)。
同理我们也可以定义三个数以及更多个数的最大公约数、最小公倍数。
定理 ∀ a , b ∈ N , g c d ( a , b ) ∗ l c m ( a , b ) a ∗ b \forall a,b \in N,gcd(a,b)*lcm(a,b)a*b ∀a,b∈N,gcd(a,b)∗lcm(a,b)a∗b 九章算数▪更相减损术 ∀ a , b ∈ N , a ≥ b , 有 g c d ( a , b ) g c d ( b , a − b ) g c d ( a , a − b ) \forall a,b \in N,a\geq b,有gcd(a,b)gcd(b,a-b)gcd(a,a-b) ∀a,b∈N,a≥b,有gcd(a,b)gcd(b,a−b)gcd(a,a−b) ∀ a , b ∈ N , 有 g c d ( 2 a , 2 b ) 2 g c d ( a , b ) \forall a,b\in N,有gcd(2a,2b)2gcd(a,b) ∀a,b∈N,有gcd(2a,2b)2gcd(a,b)
欧几里得算法 ∀ a , b ∈ N , b ≠ 0 , g c d ( a , b ) g c d ( b , a m o d b ) \forall a,b \in N,b\neq 0,gcd(a,b)gcd(b,a\ mod\ b) ∀a,b∈N,b0,gcd(a,b)gcd(b,a mod b)
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}使用欧几里得算法求最大公约数的复杂度为 O ( l o g ( a b ) ) O(log(ab)) O(log(ab))。欧几里得算法是常用的求最大公约数的方法。不过高精度除法取模不容易实现需要做高精度运算时可考虑更相减损术代替欧几里得算法。
2.互质与欧拉函数
定义 ∀ a , b ∈ N \forall a,b\in N ∀a,b∈N若 g c d ( a , b ) 1 gcd(a,b)1 gcd(a,b)1则称 a , b a,b a,b互质。
对于三个数或者更多个数的情况我们把 g c d ( a , b , c ) 1 gcd(a,b,c)1 gcd(a,b,c)1的情况称为 a , b , c a,b,c a,b,c互质。把 g c d ( a , b ) g c d ( b , c ) g c d ( c , a ) 1 gcd(a,b)gcd(b,c)gcd(c,a)1 gcd(a,b)gcd(b,c)gcd(c,a)1称为 a , b , c a,b,c a,b,c两两互质。后者显然是一个更强的条件。
欧拉函数 1 ∼ N 1\sim N 1∼N中与 N N N互质的数的个数被称为欧拉函数即为 ϕ ( N ) \phi(N) ϕ(N)。
若在算术基本定理中 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则 ϕ ( N ) N ∗ p 1 − 1 p 1 ∗ p 2 − 1 p 2 ∗ . . . ∗ p m − 1 p m N ∗ ∏ 质数 p ∣ N ( 1 − 1 p ) \phi(N)N*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*...*\frac{p_m-1}{p_m}N*\prod_{质数p|N}(1-\frac{1}{p}) ϕ(N)N∗p1p1−1∗p2p2−1∗...∗pmpm−1N∗质数p∣N∏(1−p1) 证明
设 p p p是 N N N的质因子 1 ∼ N 1\sim N 1∼N中 p p p的倍数有 p , 2 p , 3 p , . . . , ( N / p ) ∗ p p,2p,3p,...,(N/p)*p p,2p,3p,...,(N/p)∗p共 N / p N/p N/p个。同理若 q q q也是 N N N的质因子则 1 ∼ N 1\sim N 1∼N中 q q q的倍数有 N / q N/q N/q个。如果我们把这 N / p N / q N/pN/q N/pN/q个数去掉那么 p ∗ q p*q p∗q的倍数被排除了两次需要加回来一次。因此 1 ∼ N 1\sim N 1∼N不含有共同质因子 p p p或 q q q的个数为 N − N p − N q N p q N ∗ ( 1 − 1 p − 1 q 1 p q ) N ( 1 − 1 p ) ( 1 − 1 q ) N-\frac{N}{p}-\frac{N}{q}\frac{N}{pq}N*(1-\frac{1}{p}-\frac{1}{q}\frac{1}{pq})N(1-\frac{1}{p})(1-\frac{1}{q}) N−pN−qNpqNN∗(1−p1−q1pq1)N(1−p1)(1−q1) 实际上上述思想被称为容斥思想我们将在0x37节详细介绍。类似地可以在 N N N地全部质因子上使用容斥思想即可以得到 1 ∼ N 1\sim N 1∼N中不与 N N N含有任何共同质因子的数的个数也就是与 N N N互质的数的个数。
根据欧拉函数的计算式我们只需要分解质因数既可以顺便求出欧拉函数。
int phi(int n)
{int ansn;for(int i2;isqrt(n);i){if(n%i0){ansans/i*(i-1);while(n%i0) n/i;}}if(n1)ansans/n*(n-1);return ans;
}性质 1 ∼ 2 1\sim2 1∼2
1. ∀ n 1 , 1 ∼ n \forall n1,1\sim n ∀n1,1∼n中与 n n n互质的数的和为 n ∗ ϕ ( n ) / 2 n*\phi(n)/2 n∗ϕ(n)/2。
2.若 a , b a,b a,b互质则 ϕ ( a b ) ϕ ( a ) ϕ ( b ) \phi(ab)\phi(a)\phi(b) ϕ(ab)ϕ(a)ϕ(b)。
证明
因为 g c d ( n , x ) g c d ( n , n − x ) gcd(n,x)gcd(n,n-x) gcd(n,x)gcd(n,n−x)所以与 n n n不互质的数 x , n − x x,n-x x,n−x成对出现平均值为 n / 2 n/2 n/2。因此与 n n n互质的数的平均值也是 n / 2 n/2 n/2进而得到性质1。
根据欧拉函数的计算式对 a , b a,b a,b分解质因数直接可得性质2。把性质2推广到一般的函数上可以得到“积极函数”的概念。
积极函数
如果当 a , b a,b a,b互质时有 f ( a b ) f ( a ) ∗ f ( b ) f(ab)f(a)*f(b) f(ab)f(a)∗f(b)那么称函数 f f f为积极函数。
性质 3 ∼ 6 3\sim6 3∼6
3.若 f f f是积极函数且在算术基本定理中 n ∏ i 1 m p i c i n\prod_{i1}^{m}p_i^{c_i} n∏i1mpici则 f ( n ) ∏ i 1 m f ( p i c i ) f(n)\prod_{i1}^{m}f(p_i^{c_i}) f(n)∏i1mf(pici)。
4.设 p p p为质数若 p ∣ n p\mid n p∣n且 p 2 ∣ n p^2 \mid n p2∣n则 ϕ ( n ) ϕ ( n / p ) ∗ p \phi(n)\phi(n/p)*p ϕ(n)ϕ(n/p)∗p。
5.设 p p p为质数若 p ∣ n p\mid n p∣n且 p 2 ∤ n p^2\nmid n p2∤n则 ϕ ( n ) ϕ ( n / p ) ∗ ( p − 1 ) \phi(n)\phi(n/p)*(p-1) ϕ(n)ϕ(n/p)∗(p−1)。
6. ∑ d ∣ n ϕ ( d ) n \sum_{d|n}\phi(d)n ∑d∣nϕ(d)n
证明:
把 n n n分解质因数按照积极函数的定义性质3显然成立。
若 p ∣ n p\mid n p∣n且 p 2 ∣ n p^2\mid n p2∣n则 n , n / p n,n/p n,n/p包含相同的的质因子只是 p p p的质数不同。直接把 ϕ ( n ) \phi(n) ϕ(n)与 ϕ ( p / n ) \phi(p/n) ϕ(p/n)按照欧拉函数的就算公式写出二者相除商为 p p p所以性质4成立。
若 p ∣ n p\mid n p∣n且 p 2 ∤ n p^2\nmid n p2∤n则 p , n / p p,n/p p,n/p互质由 ϕ \phi ϕ是积极函数得 ϕ ( n ) ϕ ( n / p ) ∗ ϕ ( p ) \phi(n)\phi(n/p)*\phi(p) ϕ(n)ϕ(n/p)∗ϕ(p)而 ϕ ( p ) p − 1 \phi(p)p-1 ϕ(p)p−1所以性质5成立。
设 f ( n ) ∑ d ∣ n ϕ ( d ) f(n)\sum_{d\mid n}\phi(d) f(n)∑d∣nϕ(d)。用乘法分配律展开比较再利用 ϕ \phi ϕ是积极函数得到若 n , m n,m n,m互质则 f ( n m ) ∑ d ∣ n m ϕ ( d ) ( ∑ d ∣ n ϕ ( d ) ) ∗ ( ∑ d ∣ m ϕ ( d ) ) f ( n ) ∗ f ( m ) f(nm)\sum_{d\mid nm}\phi(d)(\sum_{d\mid n}\phi(d))*(\sum_{d\mid m}\phi(d))f(n)*f(m) f(nm)∑d∣nmϕ(d)(∑d∣nϕ(d))∗(∑d∣mϕ(d))f(n)∗f(m)。即 ∑ d ∣ n ϕ ( d ) \sum_{d\mid n}\phi(d) ∑d∣nϕ(d)是积极函数。对于单个质因子 f ( p m ) ∑ d ∣ p m ϕ ( d ) ϕ ( 1 ) ϕ ( p ) ϕ ( p 2 ) . . . ϕ ( p m ) f(p^m)\sum_{d\mid p^m}\phi(d)\phi(1)\phi(p)\phi(p^2)...\phi(p^m) f(pm)∑d∣pmϕ(d)ϕ(1)ϕ(p)ϕ(p2)...ϕ(pm)是一个等比数列求和再加1结果为 p m p^m pm。所以 f ( n ) ∏ i 1 m f ( p i c i ) ∏ i 1 m p i c i n f(n)\prod_{i1}^m f(p_i^{c_i})\prod_{i1}^m p_i^{c_i}n f(n)∏i1mf(pici)∏i1mpicin性质6成立。
有关积极函数还有许多内容并可延伸出狄利克雷卷积、莫比乌斯反演以及一系列相关的快速求和问题。
