学习笔记 ---- 数论分块(整除分块)

2024-09-01 20:12

本文主要是介绍学习笔记 ---- 数论分块(整除分块),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

算法

概述

数论分块可以快速计算一些含有除法向下取整的和式(即形如 ∑ i = 1 n f ( i ) g ( ⌊ n i ⌋ ) \sum_{i = 1}^{n}f(i)g(\left \lfloor \frac{n}{i}\right \rfloor) i=1nf(i)g(in))。当可以在 O ( 1 ) O(1) O(1) 或者 O ( l o g 2 n ) O(log_2n) O(log2n) 的复杂度内计算 f ( r ) − f ( l ) f(r) - f(l) f(r)f(l)时,数论分块就能在 O ( n ) O(\sqrt{n}) O(n ) O ( n l o g 2 n ) O(\sqrt{n}log_2n) O(n log2n) 的复杂度内计算出上述和式的值。

它主要利用了富比尼定理(其实没啥用,不需要懂)。核心想法是 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in 相同的数打包同时计算

引理

引理 1 1 1

∀ a , b , c ∈ Z , ⌊ a b c ⌋ = ⌊ ⌊ a b ⌋ c ⌋ \forall a,b,c \in Z,\left \lfloor \frac{a}{bc} \right \rfloor = \left \lfloor \frac{\left \lfloor \frac{a}{b} \right \rfloor}{c} \right \rfloor a,b,cZbca=cba

证明:
a b = ⌊ a b ⌋ + r ( 0 < r < 1 ) \frac{a}{b} = \left \lfloor \frac{a}{b} \right \rfloor + r(0 < r < 1) ba=ba+r(0<r<1)
⌊ a b c ⌋ = ⌊ a b c ⌋ = ⌊ ⌊ a b ⌋ c + r c ⌋ \left \lfloor \frac{a}{bc} \right \rfloor = \left \lfloor \frac{\frac{a}{b}}{c} \right \rfloor = \left \lfloor \frac{\left \lfloor \frac{a}{b} \right \rfloor}{c} + \frac{r}{c} \right \rfloor bca=cba=cba+cr
⌊ a b ⌋ = p c + q ( 0 ≤ q < c ) \left \lfloor \frac{a}{b} \right \rfloor = pc + q(0 \leq q<c) ba=pc+q(0q<c)
q + r < c q + r < c q+r<c
⌊ ⌊ a b ⌋ c + r c ⌋ = ⌊ p + q + r c ⌋ = p = ⌊ ⌊ a b ⌋ c ⌋ \left \lfloor \frac{\left \lfloor \frac{a}{b} \right \rfloor}{c} + \frac{r}{c} \right \rfloor = \left \lfloor p + \frac{q + r}{c} \right \rfloor = p = \left \lfloor \frac{\left \lfloor \frac{a}{b} \right \rfloor}{c} \right \rfloor cba+cr=p+cq+r=p=cba

引理 2 2 2

∀ n ∈ N ∗ , ∣ { ⌊ n d ⌋ ∣ d ∈ N ∗ , d ≤ n } ∣ ≤ ⌊ 2 n ⌋ \forall n \in N^{*},|\left \{ \left \lfloor \frac{n}{d} \right \rfloor | d \in N^{*},d \leq n\right \} | \leq \left \lfloor 2\sqrt{n} \right \rfloor nN,{dndN,dn}2n

证明:
对于 d ≤ ⌊ n ⌋ d \leq \left \lfloor \sqrt{n} \right \rfloor dn ⌊ n d ⌋ \left \lfloor \frac{n}{d} \right \rfloor dn 最多有 ⌊ n ⌋ \left \lfloor \sqrt{n} \right \rfloor n 种取值。
对于 d > ⌊ n ⌋ d > \left \lfloor \sqrt{n} \right \rfloor d>n ⌊ n d ⌋ \left \lfloor \frac{n}{d} \right \rfloor dn 最多有 ⌊ n ⌋ \left \lfloor \sqrt{n} \right \rfloor n 种取值。

综上,的证。

数论分块结论(区间右端点公式)

对于常数 n n n,使得式子 ⌊ n i ⌋ = ⌊ n j ⌋ \left \lfloor \frac{n}{i} \right \rfloor = \left \lfloor \frac{n}{j} \right \rfloor in=jn 成立,且 i ≤ j ≤ n i \leq j \leq n ijn 的最大的 j j j ⌊ n ⌊ n i ⌋ ⌋ \left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor}\right \rfloor inn。即 i i i 所在的区间的右端点为 ⌊ n ⌊ n i ⌋ ⌋ \left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor}\right \rfloor inn

证明:
⌊ n i ⌋ = k \left \lfloor \frac{n}{i} \right \rfloor = k in=k
j × k ≤ n j \times k \leq n j×kn
由于 j ∈ N ∗ j \in N^{*} jN,则 j ≤ ⌊ n k ⌋ = ⌊ n ⌊ n i ⌋ ⌋ j \leq \left \lfloor \frac{n}{k} \right \rfloor = \left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor} \right \rfloor jkn=inn

得证。

过程

数论分块的过程大概如下:
考虑和式: ∑ i = 1 n f ( i ) g ( ⌊ n i ⌋ ) \sum_{i = 1}^{n} f(i)g(\left \lfloor \frac{n}{i} \right \rfloor) i=1nf(i)g(in)
那么由于 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in 呈现块状分布,相同的值对应的 i i i 是连续的一段。因此这一段内 g ( ⌊ n i ⌋ ) g(\left \lfloor \frac{n}{i} \right \rfloor) g(in) 也是相等的。我们求出一段的 f f f 和,乘上对应的 g g g,就能算出一段的和。然后根据 右端点公式 跳到下一段的开头即可。由引理 2 2 2 我们知道了总段数不会超过 ⌊ 2 n ⌋ \left \lfloor 2\sqrt{n} \right \rfloor 2n ,因此复杂度是 O ( n ) O(\sqrt{n}) O(n ) 的。

模版代码:

int calc(int n) {int l = 1, r, res = 0;while(l <= n) {r = (n / (n / l)); // r为l所在段的右端点 res += (pre[r] - pre[l - 1]) * g[n / l]; // pre[i] = f[1] + f[2] + ... + f[i]l = r + 1;}return res;
}

N N N 维数论分块

什么是多维数论分块?
我们首先考虑一个和式:

∑ i = 1 m i n ( n , m ) f ( i ) g ( ⌊ n i ⌋ ) h ( ⌊ m i ⌋ ) \sum_{i = 1}^{min(n, m)}f(i)g(\left \lfloor \frac{n}{i} \right \rfloor)h(\left \lfloor \frac{m}{i} \right \rfloor) i=1min(n,m)f(i)g(in)h(im)

我们发现式子中分母有两种: n n n m m m。这时候我们把 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in ⌊ m i ⌋ \left \lfloor \frac{m}{i} \right \rfloor im 用线段图画出来,一条线段内的 i i i 表示 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in 的值相等。如下图:
在这里插入图片描述
然后我们把两条线段的所有端点拿出来作为划分整个序列的断点,如下图:

在这里插入图片描述
不难发现,此时序列里每一段中 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in 都相等, ⌊ m i ⌋ \left \lfloor \frac{m}{i} \right \rfloor im 也相等,因此我们又可以一次计算一整段的和了。但是要乘一个 2 2 2 的常数。(因为断点数乘 2 2 2,所以段数多了一倍)

上面的就算是 二维数论分块维度数 实际上就是 不同的分子数 n n n 维数论分块的复杂度是 O ( n n ) O(n\sqrt{n}) O(nn ) 的。但是一般二维数论分块最常见。

二维数论分块模版:

int calc(int n, int m) {int t = min(n, m);int l = 1, r, res = 0;while(l <= t) {r = min({n / (n / l), m / (m / l), t});res += (pre[r] - pre[l - 1]) * g[n / l] * h[m / l];l = r + 1;}return res;
}

n n n 维数论分块模版:

int calc(int n) {int t = a[1];int l = 1, r, res = 0;for(int i = 1; i <= n; i ++ ) t = min(t, a[i]);while(l <= t) {r = t;for(int i = 1; i <= n; i ++ ) {r = min(r, a[i] / (a[i] / l));}int tmp = pre[r] - pre[l - 1];for(int i = 1; i <= n; i ++ ) {tmp = tmp * f[i][a[i] / l];}res += tmp;l = r + 1;}return res;
}

向上取整的数论分块

与向下取整十分相似。核心思路相同,但是需要重新推导右端点公式。

结论:
对于常数 n n n,使得 ⌈ n i ⌉ = ⌈ n j ⌉ \left \lceil \frac{n}{i} \right \rceil = \left \lceil \frac{n}{j} \right \rceil in=jn 成立并且满足 i ≤ j ≤ n i \leq j \leq n ijn 的最大的 j j j ⌊ n − 1 ⌊ n − 1 i ⌋ ⌋ \left \lfloor \frac{n - 1}{\left \lfloor \frac{n - 1}{i} \right \rfloor} \right \rfloor in1n1,即 i i i 所在块的右端点为 ⌊ n − 1 ⌊ n − 1 i ⌋ ⌋ \left \lfloor \frac{n - 1}{\left \lfloor \frac{n - 1}{i} \right \rfloor} \right \rfloor in1n1

证明:

不难发现 ⌈ n i ⌉ = ⌊ n − 1 i ⌋ + 1 \left \lceil \frac{n}{i} \right \rceil = \left \lfloor \frac{n - 1}{i} \right \rfloor + 1 in=in1+1
这个可以讨论 n n n 是否是 i i i 的倍数来证明。
然后把 ⌈ n i ⌉ \left \lceil \frac{n}{i} \right \rceil in ⌈ n j ⌉ \left \lceil \frac{n}{j} \right \rceil jn 分别换成 ⌊ n − 1 i ⌋ + 1 \left \lfloor \frac{n - 1}{i} \right \rfloor + 1 in1+1 ⌊ n − 1 j ⌋ + 1 \left \lfloor \frac{n - 1}{j} \right \rfloor + 1 jn1+1 然后就跟向下取整是一样的了。

注意:当 i = n i = n i=n 时会出现分母为 0 0 0 的情况,需要特殊处理。

例题

H ( n ) H(n) H(n)

题意: 给你 n n n,求 ∑ i = 1 n ⌊ n i ⌋ \sum_{i = 1}^{n} \left \lfloor \frac{n}{i} \right \rfloor i=1nin

分析:没什么好说的,数论分块板子题。
CODE:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int T, n;
LL calc(int n) {int l = 1, r; LL res = 0;while(l <= n) {r = n / (n / l);res += 1LL * (r - l + 1LL) * (n / l);l = r + 1;}return res;
}
int main() {scanf("%d", &T);while(T -- ) {scanf("%d", &n);printf("%lld\n", calc(n));}return 0;
}

[CQOI2007] 余数求和

点这里
题意: 给出正整数 n n n k k k。求 G ( n , k ) = ∑ i = 1 n k m o d i G(n, k) = \sum_{i = 1}^{n} k \ mod \ i G(n,k)=i=1nk mod i 1 ≤ n , k ≤ 1 0 9 1 \leq n,k \leq 10^9 1n,k109

分析:
G ( n , k ) = ∑ i = 1 n k − i × ⌊ k i ⌋ = n × k − ∑ i = 1 n i × ⌊ k i ⌋ G(n, k) = \sum_{i = 1}^{n} k - i\times \left \lfloor \frac{k}{i} \right \rfloor = n\times k - \sum_{i = 1}^{n} i \times \left \lfloor \frac{k}{i} \right \rfloor G(n,k)=i=1nki×ik=n×ki=1ni×ik

然后一维数论分块即可。复杂度 O ( m i n ( n , k ) ) O(\sqrt{min(n, k)}) O(min(n,k) )

CODE:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, k, res;
int main() {cin >> n >> k;res = n * k;LL l = 1, r;while(l <= min(n, k)) {r = min(n, k / (k / l));res = res - (r - l + 1LL) * (l + r) / 2LL * (k / l);l = r + 1LL;}cout << res << endl;return 0;
}

[清华集训2012] 模积和

点这里

题意: 求 ∑ i = 1 n ∑ j = 1 m ( n m o d i ) × ( m m o d j ) , i ≠ j \sum_{i = 1}^{n} \sum_{j = 1}^{m} (n \ mod \ i) \times (m \ mod \ j), i \ne j i=1nj=1m(n mod i)×(m mod j),i=j。对 19940417 19940417 19940417 取模。

1 ≤ n , m ≤ 1 0 9 1 \leq n,m \leq 10^9 1n,m109

分析:
简单题。
首先通过容斥满足 i ≠ j i \ne j i=j 的限制,答案就是:

∑ i = 1 n ∑ j = 1 m ( n m o d i ) × ( m m o d j ) − s u m i = 1 m i n ( n , m ) ( n m o d i ) × ( m m o d i ) \sum_{i = 1}^{n} \sum_{j = 1}^{m}(n \ mod \ i) \times (m \ mod \ j) - sum_{i = 1}^{min(n, m)}(n \ mod \ i) \times (m \ mod \ i) i=1nj=1m(n mod i)×(m mod j)sumi=1min(n,m)(n mod i)×(m mod i)

分开开两个式子。
对于左边:
∑ i = 1 n ∑ j = 1 m ( n m o d i ) × ( m m o d j ) \sum_{i = 1}^{n} \sum_{j = 1}^{m} (n \ mod \ i) \times (m \ mod \ j) i=1nj=1m(n mod i)×(m mod j)
= ∑ i = 1 n ∑ j = 1 m ( n − i × ⌊ n i ⌋ ) × ( m − j × ⌊ m j ⌋ ) = \sum_{i = 1}^{n}\sum_{j = 1}^{m}(n - i\times \left \lfloor \frac{n}{i} \right \rfloor) \times (m - j\times \left \lfloor \frac{m}{j} \right \rfloor) =i=1nj=1m(ni×in)×(mj×jm)
= s u m i = 1 n ∑ j = 1 m n m − n j × ⌊ m j ⌋ − m i × ⌊ n i ⌋ + i j × ⌊ n i ⌋ × ⌊ m j ⌋ = sum_{i = 1}^{n}\sum_{j = 1}^{m} nm - nj \times \left \lfloor \frac{m}{j} \right \rfloor - mi \times \left \lfloor \frac{n}{i} \right \rfloor + ij \times \left \lfloor \frac{n}{i} \right \rfloor \times \left \lfloor \frac{m}{j} \right \rfloor =sumi=1nj=1mnmnj×jmmi×in+ij×in×jm
= n 2 m 2 − n 2 ∑ j = 1 m j × ⌊ m j ⌋ − m 2 ∑ i = 1 n i × ⌊ n i ⌋ + ∑ i = 1 n ( i × ⌊ n i ⌋ ) × ∑ j = 1 m ( j × ⌊ m j ⌋ ) =n^2m^2 -n^2\sum_{j = 1}^{m}j\times \left \lfloor \frac{m}{j} \right \rfloor - m^2\sum_{i = 1}^{n}i\times \left \lfloor \frac{n}{i} \right \rfloor + \sum_{i = 1}^{n}(i \times\left \lfloor \frac{n}{i} \right \rfloor) \times \sum_{j = 1}^{m}(j \times \left \lfloor \frac{m}{j} \right \rfloor) =n2m2n2j=1mj×jmm2i=1ni×in+i=1n(i×in)×j=1m(j×jm)

化简到这一步后,显然每一个求和符号都可以用数论分块在 O ( n ) O(\sqrt{n}) O(n ) 的时间内求出。

再看右边:
∑ i = 1 m i n ( n , m ) ( n m o d i ) × ( m m o d i ) \sum_{i = 1}^{min(n, m)}(n \ mod \ i) \times (m \ mod \ i) i=1min(n,m)(n mod i)×(m mod i)
= ∑ i = 1 m i n ( n , m ) ( n − i × ⌊ n i ⌋ ) × ( m − i × ⌊ m i ⌋ ) = \sum_{i = 1}^{min(n, m)}(n - i \times\left \lfloor \frac{n}{i} \right \rfloor) \times (m - i \times \left \lfloor \frac{m}{i} \right \rfloor) =i=1min(n,m)(ni×in)×(mi×im)
m i n ( n , m ) = t min(n, m) = t min(n,m)=t,则原式
= ∑ i = 1 t n m − n i × ⌊ m i ⌋ − m i × ⌊ n i ⌋ + i 2 × ⌊ n i ⌋ × ⌊ m i ⌋ =\sum_{i = 1}^{t}nm - ni \times \left \lfloor \frac{m}{i} \right \rfloor - mi \times \left \lfloor \frac{n}{i} \right \rfloor + i^2 \times \left \lfloor \frac{n}{i} \right \rfloor \times \left \lfloor \frac{m}{i} \right \rfloor =i=1tnmni×immi×in+i2×in×im
= n m t − n × ∑ i = 1 t i × ⌊ m i ⌋ − m × ∑ i = 1 t i × ⌊ m i ⌋ + ∑ i = 1 t i 2 × ⌊ m i ⌋ × ⌊ n i ⌋ =nmt - n\times \sum_{i = 1}^{t}i\times \left \lfloor \frac{m}{i} \right \rfloor - m \times \sum_{i = 1}^{t} i \times \left \lfloor \frac{m}{i} \right \rfloor + \sum_{i = 1}^{t} i^2 \times \left \lfloor \frac{m}{i} \right \rfloor \times \left \lfloor \frac{n}{i} \right \rfloor =nmtn×i=1ti×imm×i=1ti×im+i=1ti2×im×in

然后就是前两个求和符号非常简单,直接一维整除分块即可。最后一个求和符号需要二维整除分块,并且还需要快速计算出 ∑ i = l r i 2 \sum_{i = l}^{r} i^2 i=lri2

f ( r ) = ∑ i = 1 r i 2 f(r) = \sum_{i = 1}^{r} i^2 f(r)=i=1ri2,那么 s u m i = l r i 2 = f ( r ) − f ( l − 1 ) sum_{i = l}^{r}i^2 = f(r) - f(l - 1) sumi=lri2=f(r)f(l1)。然后就是有一个公式:
∑ i = 1 n i 2 = n × ( n + 1 ) × ( 2 n + 1 ) 6 \sum_{i = 1}^{n}i^2 = \frac{n \times (n + 1) \times (2n + 1)}{6} i=1ni2=6n×(n+1)×(2n+1)。有了这个我们就可以 O ( 1 ) O(1) O(1) 求出 f f f 了,这样这个题就做完了。

时间复杂度 O ( n ) O(\sqrt{n}) O(n )

CODE:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 19940417;
LL n, m, res;
inline LL get(LL x, LL y) { // x 是循环上界,y是分子 LL l = 1, r; LL res = 0;while(l <= x) {r = min(x, y / (y / l));res = (res + 1LL * ((l + r) * (r - l + 1LL) / 2LL) % mod * (y / l) % mod) % mod;l = r + 1LL;}return res;
}
LL solve(LL n) { // \sum_{i = 1}^{n} i^2LL x = n, y = n + 1LL, z = 2LL * n + 1LL;if(x % 2 == 0) x /= 2LL;else if(y % 2 == 0) y /= 2LL;else z /= 2LL;if(x % 3 == 0) x /= 3LL;else if(y % 3 == 0) y /= 3LL;else z /= 3LL;return x * y % mod * z % mod;
}
inline LL calc(LL t, LL n, LL m) { // 二维数论分块, t是上界 LL l = 1, r; LL res = 0;while(l <= t) {r = min({t, n / (n / l), m / (m / l)});res = (res + ((solve(r) - solve(l - 1)) % mod + mod) % mod * (n / l) % mod * (m / l) % mod) % mod;l = r + 1LL;}return res;
}
int main() {cin >> n >> m;LL t1 = ((m * m % mod - get(m, m)) % mod + mod) % mod;LL t2 = ((n * n % mod - get(n, n)) % mod + mod) % mod;res = t1 * t2 % mod;LL t = min(n, m);LL del = n * m % mod * t % mod;del = ((del - n * get(t, m) % mod) % mod + mod) % mod;del = ((del - m * get(t, n) % mod) % mod + mod) % mod;del = (del + calc(t, n, m)) % mod;res = ((res - del) % mod + mod) % mod;cout << res << endl;return 0;
}

这篇关于学习笔记 ---- 数论分块(整除分块)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1127930

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7