Q779’s Blog

洛谷P2522 [HAOI2011]Problem b 题解 题目链接：P2522 [HAOI2011]Problem b 题意：对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a \le x \le b\)，\(c \le y \le d\)，且 \(\gcd(x,y) = k\)，\(\gcd(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。 一句话题意： 求 \[ \sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)=k] \] 根据容斥原理，不妨令 \[ F(n,m) = \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] \] 则答案为 \[ F(b,d)-F(b,c-1)-F(a-1,d)+F(a-1,c-1) \] 然后推推柿子 \[ \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] \\&=\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\...

洛谷P2568 GCD 题解 题目链接：P2568 GCD 题意： 给定正整数 \(n\)，求 \(1\le x,y\le n\) 且 \(\gcd(x,y)\)为素数的数对 \((x,y)\) 有多少对。 \(1 \le n\le 10^7\) 正着去想不太好搞，那就反过来 考虑一个素数对答案的贡献 显然所有满足条件的 \((x,y)\) 都可以写作 \((ap_i,bp_i)\) 的形式，其中 \(\gcd(x,y)=p_i\) 注意到 \(\gcd(a,b)=1\) 则对于每个素数 \(p\ (p\le n)\) ，它对答案的贡献就是 \[ 2\sum\limits_{i=1}^{k}\varphi(i)-1 \] 其中，\(k=\left\lfloor\dfrac{n}{p}\right\rfloor\)， \(\varphi(n)\) 为欧拉函数 \(\times 2\) 是因为 \((x,y)\) 为有序点对，\(-1\) 是因为 \((1,1)\) 会被多算一次 直接线性筛 \(\varphi(n)\) 然后前缀和一下就好了 时间复杂度 \(O(n)\) ，记得...

洛谷P2613 【模板】有理数取余 题解 题目链接：P2613 【模板】有理数取余 题意：给出 \(c=\frac{a}{b}\) ，求 \(\frac{a}{b} \bmod 19260817\) \(0 \le a \le 10^{10001},1\le b \le 10^{10001}\) 令 \(m=19260817\) 注意这里模意义下的有理数其实就是 \[ \frac{a}{b} \pmod m = ab^{-1} \pmod m \] 简单推推柿子吧 显然有 \[ bc \equiv a \pmod{m} \] 令 \[ b_0=b \bmod m,a_0 = a \bmod m \] 当 \(b_0 \ne 0\) 即 \(m \nmid b\) 时，有 \[ c \equiv a_0 b_0^{-1} \pmod{m} \] 那么exgcd一下就出来了 当 \(b_0=0\) 即 \(m \mid b\) 时，分类讨论 当 \(m \mid a\) 时， \(\forall c \in \Z,bc \equiv a \pmod{m}\) 恒成立，题目保证...

洛谷P2738 [USACO4.1]篱笆回路Fence Loops 题解 题目链接：P2738 [USACO4.1]篱笆回路Fence Loops 题意：农夫布朗的牧场上的篱笆已经失去控制了。它们分成了1~200英尺长的线段。只有在线段的端点处才能连接两个线段，有时给定的一个端点上会有两个以上的篱笆。结果篱笆形成了一张网分割了布朗的牧场。布朗想将牧场恢复原样，出于这个考虑，他首先得知道牧场上哪一块区域的周长最小。 布朗将他的每段篱笆从1到N进行了标号（N=线段的总数）。他知道每段篱笆有如下属性： 该段篱笆的长度 该段篱笆的一端所连接的另一段篱笆的标号 该段篱笆的另一端所连接的另一段篱笆的标号 幸运的是，没有篱笆连接它自身。对于一组有关篱笆如何分割牧场的数据，写一个程序来计算出所有分割出的区域中最小的周长。 例如，标号1~10的篱笆由下图的形式组成（下面的数字是篱笆的标号）： 1 +---------------+ |\ /| 2| \7 / | | \ / | +---+ / ...

洛谷P2888 [USACO07NOV]Cow Hurdles S 题解 题目链接：P2888 [USACO07NOV]Cow Hurdles S 题意：Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。 奶牛的训练场中有 \(N (1 ≤ N ≤ 300)\) 个站台，分别标记为 \(1\dots N\) 。所有站台之间有 \(M (1 ≤ M ≤ 25,000)\) 条单向路径，第i条路经是从站台 \(S_i\) 开始，到站台 \(E_i\) ，其中最高的栏的高度为\(H_i (1 ≤ H_i ≤ 1,000,000)\)。无论如何跑，奶牛们都要跨栏。 奶牛们有 \(T (1 ≤ T ≤ 40,000)\) 个训练任务要完成。第 \(i\) 个任务包含两个数字 \(A_i\) 和 \(B_i (1 ≤ A_i ≤ N; 1 ≤ B_i ≤ N)\)，表示奶牛必须从站台 \(A_i\) 跑到站台 \(...

洛谷P2912 [USACO08OCT]Pasture Walking G 题解 题目链接：P2912 [USACO08OCT]Pasture Walking G 题意：有 \(N(2\le N\le1000)\) 头奶牛，编号为 \(1\) 到 \(W\) ，它们正在同样编号为 \(1\) 到 \(N\) 的牧场上行走.为了方便，我们假设编号为 \(i\) 的牛恰好在第 \(i\) 号牧场上. 有一些牧场间每两个牧场用一条双向道路相连，道路总共有 \(N - 1\) 条，奶牛可以在这些道路 上行走.第 \(i\) 条道路把第 \(A_i\) 个牧场和第 \(B_i\) 个牧场连了起来 \((1 \le A_i \le N; 1 \le B_i \le N)\) ，而它的长度 是 \(1 \le L_i \le 10,000\).在任意两个牧场间，有且仅有一条由若干道路组成的路径相连.也就是说，所有的道路构成了一棵树. 奶牛们十分希望经常互相见面.它们十分着急，所以希望你帮助它们计划它们的行程，你只 需要计算出 \(Q(1 < Q < 1000)\) 对点之间的路径...

洛谷P3188 [HNOI2007]梦幻岛宝珠 题解 题目链接：P3188 [HNOI2007]梦幻岛宝珠 题意： 给你 \(n\) 颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过 \(W\)，且总价值最大，并输出最大的总价值。 【数据范围】 对于 \(100\%\) 的数据，\(1\le n \le 100\)，\(1\le W,w_i,v_i \le 2^{30}\)。 保证每个 \(w_i\) 能写成 \(a \times 2^b\space (a,b \in \mathbb N)\) 的形式，\(a \leq 10\) , \(b \leq 30\)，且答案不超过 \(2^{30}\)。 注：下文中将使用 \(m\) 代替 \(W\)。 这么大的背包容量，肯定不是朴素的背包问题 可以发现数据范围里强调了 “保证每个 \(w_i\) 能写成 \(a \times 2^b\space (a,b \in \mathbb N)\) 的形式” 尽管有 \[ \forall\, x \in \mathbb{N},\exist\, a,b \in \...

洛谷P3297 [SDOI2013] 逃考 题解 题目链接：P3297 [SDOI2013] 逃考 题意：髙考又来了，对于不认真读书的小杨来讲，真不是个好消息。为了小杨能在家里认真读书，他的亲戚决定驻扎在他的家里监督他学习，有爷爷奶奶、外公外婆、大舅、大嫂、阿姨…… 小杨实在是忍无可忍了，这种生活跟监狱有什么区别！为了他亲爱的小红，为了他的dota,他决定越狱！ 假设小杨的家是个 \(x_1\times y_1\) 的矩阵，左下角坐标为 \((0,0)\) ，右上角坐标为 \((x_1,y_1)\) 。小杨有 \(n\) 个亲戚，驻扎在矩阵里（位置不同，且不在矩阵的边上）。小杨家里的每个地方都被亲戚监控着，而且只被距离最近的亲戚监控： 也就是说假设小杨所在的位置是 \((3,3)\) ，亲戚A在 \((3,0)\) ， A距离小杨距离是 \(3\)；亲戚B在 \((6,7)\) ，则B距离小杨距离是 \(5\) 。距离A<距离B，所以 \((3,3)\) 位置由A监控。 如果“最近距离”出现同时有几个亲戚，那么那个位置同时被那几个亲戚监控。 给出小杨的坐标 \((x_0,...

洛谷P3327 [SDOI2015]约数个数和 题解 题目链接：P3327 [SDOI2015]约数个数和 题意： 设 \(d(x)\) 为 \(x\) 的约数个数，给定 \(n,m\)，求 \[ \sum_{i=1}^n\sum_{j=1}^md(ij) \] 输入格式： 输入文件包含多组测试数据。 第一行，一个整数 \(T\)，表示测试数据的组数。 接下来的 \(T\) 行，每行两个整数 \(n,m\)。 输出格式： \(T\) 行，每行一个整数，表示你所求的答案。 数据范围： \(1\le T,n,m \le 50000\)。 感觉我前几篇题解的无解释推导有点不可读 所以这篇还是写的清楚一点叭 这题需要一个引理（感觉没必要记住证明的方法） 引理：设 \(d(x)\) 为 \(x\) 的约数个数，则有 \[ d(ij)=\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1] \] 证明：摘自 https://siyuan.blog.luogu.org/solution-p3327 我们考虑把每个因子一一映射。 如果 \(ij\) 的因子 ...

洛谷P3336 [ZJOI2013]话旧 题解 题目链接：P3336 [ZJOI2013]话旧 题意：小林跟着银河队选手去了一趟宇宙比赛，耳濡目染，变得学术起来。回来后，他发现世界大变样了。比丘兽究级进化，成了凤凰兽；金先生因为发了一篇 paper，一跃成为教授，也成为了银河队选拔委员会成员。 一日，小林与金教授聊天。金教授回忆起过去的岁月，那些年他学过的电路原理。他曾经对一种三角波很感兴趣，并且进行了一些探究。小林感到很好奇，于是金教授就将课题形式化地说了一遍。 有一定义在 \([0,N]\) 的连续函数 \(f(x)\)，其中 \(N\) 是整数，满足 \(f(0)=f(N)=0\)，它的所有极值点在整数处取到，且 \(f(x)\) 的极小值均是 \(0\)。对于任意的 \(0\) 到 \(N-1\) 间的整数 \(I\)，\(f(x)\) 在 \((I, I+1)\) 上是斜率为 \(1\) 或 \(-1\) 的一次函数。 金先生研究的是，若他知道其中 \(K\) 个整点的函数值，那么： 有多少个函数满足条件？ 满足条件的函数中，\(f(x)\) 的最大值，最大能是多少...

洛谷P3747 [六省联考 2017] 相逢是问候 题解 题目链接：洛谷P3747 [六省联考 2017] 相逢是问候 题意：B 君希望以维护一个长度为 \(n\) 的数组，这个数组的下标为从 \(1\) 到 \(n\) 的正整数。 一共有 \(m\) 个操作，可以分为两种： 0 l r 表示将第 \(l\) 个到第 \(r\) 个数（ \(a_l,a_{l+1} ...a_r\)）中的每一个数 \(a_i\) 替换为 \(c^{a_i}\) ，即 \(c\) 的 \(a_i\) 次方，其中 \(c\) 是输入的一个常数，也就是执行赋值 \(a_i = c^{a_i}\)。 1 l r 求第 \(l\) 个到第 \(r\) 个数的和，也就是输出： \(\sum_{i=l}^{r}a_i\) 因为这个结果可能会很大，所以你只需要输出结果 \(\bmod \ p\) 的值即可。 建议先去做一做 P4139 和 P4145 ，这道题就是这俩的综合加强版本 题解在这里 link1 link2 有个结论 \[ O(\varphi^* (p)=1)=O(\log p) \] 注：这里...

洛谷P3935 Calculating 题解 题目链接：P3935 Calculating 题意： 若 \(n\) 的分解质因数结果为 \(\prod_{i=1}^{s}p_i^{k_i}\) 令 \(f(n) = \prod_{i=1}^{s}(k_i+1)\) 求 \[ \sum\limits_{i=l}^{r}f(i) \bmod 998244353 \] 根据容斥原理，可以把答案分为两个部分 \[ \sum_{i=l}^{r}f(i) = \sum_{i=1}^{r}f(i) - \sum_{i=1}^{l-1}f(i) \] 然后推推柿子 \[ \begin{aligned} \sum_{i=1}^{r}f(i) &= \sum_{i=1}^{r}\prod_{j=1}^{s_i}{(k_{ij}+1)} \\&=\sum_{i=1}^{r}\sum_{d\mid i}1 \\&=\sum_{i=1}^{r}\left\lfloor\dfrac{r}{i}\right\rfloor \end{aligned} \] 于是有 \[ \sum_{...