Q779’s Blog

阶与原根 前置知识：欧拉定理、费马小定理、拉格朗日定理。 模板题：P6091 【模板】原根 题意： 给定整数 \(n\)，求它的所有原根。 为了减小你的输出量，给出输出参数 \(d\)，设 \(n\) 的所有原根有 \(c\) 个，从小到大分别为 \(g_1,\ldots,g_c\)，你只需要依次输出 \(g_d,g_{2d},\ldots,g_{\lfloor\frac{c}{d}\rfloor\times d}\)。 正整数 \(g\) 是正整数 \(n\) 的原根，当且仅当 \(1\leq g\leq n-1\)，且 \(g\) 模 \(n\) 的阶为 \(\varphi(n)\)。 输入格式： 本题包含多组数据。 第一行：一个整数 \(T\)，表示数据组数。 接下来 \(T\) 行：每行两个整数 \(n,d\)，表示一组询问数据。 输出格式： 对于每组数据： 第一行输出一个整数 \(c\)，表示 \(n\) 的原根个数，第二行输出 \(\lfloor\dfrac{c}{d}\rfloor\) 个数，按照题目描述中要求输出。 注意：即使 \(\lfloor\dfrac{c...

拉格朗日定理 拉格朗日定理（数论） 设 \(p\) 为素数，对于模 \(p\) 意义下的整系数多项式 \[ f(x) = a_n x^n+a_{n-1} x^{n-1}+\cdots+a_0 \,(p \not\mid a_n) \] 的同余方程 \(f(x)\equiv 0 \pmod{p}\) 在模 \(p\) 意义下至多有 \(n\) 个不同解。 证明： 考虑对 \(n\) 归纳法证明。当 \(n=0\) 时，由于 \(p \not\mid a_0\) ， 故 \(f(x) \equiv 0 \pmod{p}\) 无解，定理对 \(n=0\) 的多项式 \(f(x)\) 都成立。 若命题对于 \(\operatorname{deg} f < n\) 的 \(f\) 都成立（这里 \(\operatorname{deg}\) 表示多项式的次数） 由反证法，假设存在一个满足题目条件的 \(f\) 在模 \(p\) 意义下有着至少 \(n + 1\) 个不同的解 \(x_0,x_1,\cdots,x_n\) 。 可设 \(f(x) - f(x_0) = (x - x_0)...

洛谷P2210 Haywire 题解 题目链接：P2210 Haywire 题意： Farmer John有 \(N\) 只奶牛（\(4 \leq N \leq 12\)，\(N\) 是偶数）。 他们建立了一套原生的系统，使得奶牛与他的朋友可以通过由干草保护的线路来进行对话交流。 每一头奶牛在这个牧场中正好有 \(3\) 个朋友，并且他们必须把自己安排在一排干草堆中。 一条长 \(L\) 的线路要占用刚好 \(L\) 堆干草来保护线路。 比如说，如果有两头奶牛分别在草堆 \(4\) 与草堆 \(7\) 中，并且他们是朋友关系，那么我们就需要用 \(3\) 堆干草来建造线路，使他们之间能够联系。 假设每一对作为朋友的奶牛都必须用一条单独的线路来连接，并且我们可以随便地改变奶牛的位置，请计算出我们建造线路所需要的最少的干草堆。 简化题意：找到一个排列，使得所有边的长的总和最小，边的长取决于他们在排列中的距离。 输入格式： 第 \(1\) 行：一个整数 \(N\)。为了方便，我们给奶牛用 \(1\sim N\) 的数字进行编号。 第 \(2, 3, \cdots, N + 1\) 行...

小蓝书 17.4 题解 传送门：小蓝书 17.4 第一部分 例题 例4 由于书上例1,2,3都是基础概念，所以直接从例4开始讲。 某 \(15\) 座城市，他们之间的航线分数三家航空公司。一直无论哪家航空公司停飞，旅客总还能从任意城市飞往其他任何城市（允许转机），那么至少需要多少条航线。 解： 记三家航空公司的航线数分别为 \(a,b,c\) ，显然有 \[ a + b \ge 14 \,\land\, a + c \ge 14 \,\land\, b + c\ge 14 \] 合并一下就是 \[ a + b + c \ge 21 \] 因此需要至少 \(21\) 条航线。容易构造出几个例子，如下 其实也容易证明，上图的构造方式具有一般性，对于 \(n > 2\) 。 例5 咕咕咕。。 第二部分 习题 咕咕咕。。

小蓝书 17.4 小蓝书上 17.4 主要讲了讲树的一些性质 树，想必大家都很熟悉了，所以这篇文章不打算再讲，我们主要来讲例题。 不过有个东西可以提一下，小蓝书提到了闭链的概念，定义为一条链的开头与结尾相同。 这不意味着闭链就是环，因为环强调了这条闭链上的每个顶点互不相同。 练习题 详见 小蓝书 17.4 题解 题外话： 可能有细心的同学发现，最近我的文章变多了，但是很多都比较水，这是怎么回事呢？ 对于小蓝书系列的，我主要是开坑，以后慢慢填。 对于题解，最近确实主要刷的是基础题，不过主要是为了尽快达到每月题解量的提升。 因为我有个习惯，只要是认真学的月份必须要比上个月写的多。 如果我一个月写了 40 多篇，那我下个月无论怎么样都会尽量写到 50 篇以上。 那么基础题写多了就会去尝试难一点的题，是吧。 另外，我一直觉得我刷了这么多题为什么还是不会的很大原因是，我吸收到的经验和知识比较少 客观的讲，这其实不那么容易总结出真正的原因，但是也只能先这么认为了。 总之我现在的战术是题海战术，也就是不死磕难题，尽量刷我认为适当难度的题目。 当然了，我也不觉得我的文章很水，只是把原来的长篇...

自适应辛普森法 模板题：P4525 【模板】自适应辛普森法 1 题意： 试计算积分 \[ \displaystyle{\int_L^R\frac{cx+d}{ax+b}\,\mathrm{d}x} \] 结果保留至小数点后 \(6\) 位。 数据保证计算过程中分母不为 \(0\) 且积分能够收敛。 输入格式： 一行，包含 \(6\) 个实数 \(a,b,c,d,L,R\)。 输出格式： 一行，积分值，保留至小数点后 \(6\) 位。 数据范围： \(a,b,c,d\in[-10,10]\)，\(-100\le L<R\le 100\) 且 \(R-L\ge1\)。 先给出 Simpson 公式 \[ \int_a^b f(x) \,\mathrm{d} x \,\approx\,(b-a)\cdot \frac{f(a)+4 f\left(\frac{a+b}{2}\right)+f(b)}{6} \] 下面给出推导和介绍 Simpson 公式的原理在于用二次函数去拟合区间，并计算定积分。 显然，区间划分的越多，精确度也就相对越高，不过相应的时间复杂度也会增大。 不过...

小蓝书 17.3 \(k\) 部图： 若图 \(G=(V,E)\) 的点集 \(V\) 可以被分解为 \(k\) 个两两不交非空子集的并，并且没有任何一条边的两个端点都在同一个子集中，则称 \(G\) 为 \(k\) 部图 ，记作 \(G = (V_1,V_2,\cdots,V_k;E)\) 。 完全 \(k\) 部图： 若 \(k\) 部图 \(G = (V_1,V_2,\cdots,V_k;E)\) 中，任何两点 \(u \in V_i,v \in V_j, i \ne j\) 均有 \((i,j) \in E\) ，则称 \(G\) 为完全 \(k\) 部图 图的直径： 记 \(d(u,v)\) 表示 \(u\) 到 \(v\) 的一条最短路径的长，则图的直径为 \(\max_{u\ne v} d(u,v)\) 。 托兰定理： 若 \(G\) 是一个有 \(n\) 个顶点的图，且完全图 \(K_{r+1}\) 不是 \(G\) 的子图，则 \(G\) 最多有 \(\frac{r-1}{r}\cdot \frac{n^2}{2} = \left(1-\frac{1}{r}\r...

放缩法 放缩法是通过舍去或添加一些项来构造不等式的一种方法。 说了跟没说一样，我们来看几个例题。 例题1： 求证 \[ \sqrt{\log _2 3}+\sqrt{\log _3 2}<\sqrt{2}+1 \] 证明：构造以下不等式 \[ \sqrt{\log _2 3}+\sqrt{\log _3 2}<\sqrt{\log _2 4}+\sqrt{\log _3 3}=\sqrt{2}+1 \] 例题2： 求证 \[ \sum_{k=1}^n \frac{1}{k^2}<2-\frac{1}{n} \] 证明：构造以下不等式 \[ \sum_{k=1}^n \frac{1}{k^2}<1+\sum_{k=2}^n \frac{1}{k(k-1)}=1+\sum_{k=2}^n \frac{1}{k-1}-\frac{1}{k}=2-\frac{1}{n} \] 好，后面的例题就比较复杂，没什么意义。 看到这里，放缩法其实已经显露原形了，就是我们常用到的，构造一个比较简易的边界。 当然不是所有这样的边界都很容易找到，但是这个方法还是有必要理解的...

小蓝书 17.2 喜欢水文章。 度数 与一个顶点 \(v\) 关联的边的条数称作该顶点的 度 (degree)，记作 \(d(v)\)。特别地，对于边 \((v, v)\)，则每条这样的边要对 \(d(v)\) 产生 \(2\) 的贡献。 对于无向简单图，有 \(d(v) = \left| N(v) \right|\)。 握手定理（又称图论基本定理）：对于任何无向图 \(G = (V, E)\)，有 \(\sum_{v \in V} d(v) = 2 \left| E \right|\)。 推论：在任意图中，度数为奇数的点必然有偶数个。 若 \(d(v) = 0\)，则称 \(v\) 为 孤立点 (isolated vertex)。 若 \(d(v) = 1\)，则称 \(v\) 为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)。 若 \(2 \mid d(v)\)，则称 \(v\) 为 偶点 (even vertex)。 若 \(2 \nmid d(v)\)，则称 \(v\) 为 奇点 (odd vertex)。任意图中奇点的个数是偶数。 若 \...

巴塞尔问题（\(\zeta(2)=\frac{\pi}{6}\)） 巴塞尔问题是一个著名的数论问题，这个问题首先由皮耶特罗·门戈利在1644年提出，由莱昂哈德·欧拉在1735年解决。由于这个问题难倒了以前许多的数学家，年仅二十八岁的欧拉因此一举成名。欧拉把这个问题作了一番推广，他的想法后来被黎曼在1859年的论文《论小于给定大数的素数个数》(On the Number of Primes Less Than a Given Magnitude) 中所采用，论文中定义了黎曼 \(ζ\) 函数，并证明了它的一些基本的性质。这个问题是以瑞士的第三大城市巴塞尔命名的，它是欧拉和伯努利家族的家乡。 上面是背景故事，简单来说就是求以下级数的精确值 \[ \sum_{n=1}^{\infty} \frac{1}{n^2}=\lim _{n \rightarrow+\infty}\left(\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{n^2}\right) \] 不着急，我们先来证明该级数是收敛的。 注意到任意整数 \(n\,(n\ge 2)\) 有...

洛谷P9148 除法题 题解 题目链接：P9148 除法题 题意： 给定大小为 \(n\) 的集合 \(a\)，保证其中元素互不相同且均为正整数。 如果我们从中按顺序取出三个元素 \(a, b, c\)，则共有 \(n \cdot (n-1) \cdot (n-2)\) 种不同的选择方案。 现在对于一种选择方案 \((a,b,c)\)，定义其权值为 \(\Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor\Bigl\lfloor\dfrac{a}{c}\Bigr\rfloor\Bigl\lfloor\dfrac{b}{c}\Bigr\rfloor\)。 你需要对所有的选择方案计算权值的总和，你只需输出这个总和对 \(2^{32}\) 取模的结果。 注：\(\lfloor a\rfloor\) 表示不大于 \(a\) 的最大整数。如 \(\lfloor 2.4\rfloor=2\)、\(\lfloor 5\rfloor=5\)。 输入格式： 第一行，一个正整数 \(n\)，表示序列的长度。 第二行，\(n\) 个正整数 \(a_1, a_2, \ldots, ...

九连环的数学原理 最近正好看到一道题跟九连环有关，而自己连九连环都不会 所以今天就来写一篇文章讲讲九连环的数学原理吧。 顺便搬了一个 javascript 写的模拟器，直接访问点这里，相关文章点这里 不妨记环在杆子上则状态为 \(1\) ，反之为 \(0\) ，并用 \(a_i\) 表示环 \(i\) 的状态。 稍微玩一玩可以发现，九连环有且仅有两种操作方式 改变位置最左侧的环的那个状态 改变位置为 \(i~(2 \le i \le 9)\) 的环，且 \(i\) 满足 \(a_{i-1} = 1 \,\land\,\forall 1\le j <i-1,~a_j=0\) 。 操作二可能不太形象，但是如果大家手头有九连环的话应该就知道怎么取出来了。 那么怎么解开这个九连环呢？容易发现，上述两个操作均为可逆操作，且不存在其他更多的操作方式。 这里操作的可逆性体现在 \(S_n\cdot A \cdot A = S_n\) ，也就是重复两次同一操作可以变回原状态，这点很显然。 因此只有 \(A,B,A,B\) 的操作和 \(B,A,B,A\) 的操作可以让九连环的状态...