Q779’s Blog

数学常数表 常数表 \(e = \tt{2.718281828}\) \(\pi = \tt{3.141592654}\) \(\ln \pi = \tt{1.1447}\) \(\sqrt{\pi} = \tt{1.7725}\) 自然对数表 \(N\) \(\ln N\) \(\ln2 = \tt{0.69}\) \(\tt{2}\) \(\tt{0.6931}\) \(\ln3 = \tt{1.10}\) \(\tt{3}\) \(\tt{1.0986}\) \(\ln5 = \tt{1.61}\) \(\tt{5}\) \(\tt{1.6094}\) \(\ln7 = \tt{1.95}\) \(\tt{7}\) \(\tt{1.9459}\) \(\ln11 = \tt{2.40}\) \(\tt{11}\) \(\tt{2.3979}\) \(\ln13 = \tt{2.56}\) \(\tt{13}\) \(\tt{2.5649}\) \(\ln17 = \tt{2.83}\) \(\tt{17}\) \(\tt{2.8332}...

CF906D Power Tower 题解 题目链接：CF906D Power Tower 题意：给定长度为 \(n\) 的序列 \(a_i\) 和模数 \(p\) \(Q\) 次询问区间 \([l,r]\) 的 \[ a_l^{ {a_{l+1}^{ {a_{l+2}^{ ^{ {.}^{ {.}^{ {.}^{ {a_{r} } } } } } } } } } } \] \(1 \le n \le 10^5,~1 \le p,a_i \le 10^9,~1\le Q \le 10^5\) 显然扩展欧拉定理的应用 关于 \(O(\varphi^*(n)=1)\approx O(\log n)\) 的证明，可以看这里 link 注：这里的 \(O(\varphi^*(n)=1)\) 指最小的 \(x\) 使得 \(\varphi^{x}(n)=1\) 因此对于每个询问，我们直接从左往右跑就好了，递归实现 注意快速幂要满足扩欧的性质哦，不要乱模 时间复杂度 \(O(Q \log \max\{a_i\})\) 代码： #include <iostream> #include...

2.3 和式的处理 一、定律 设 \(K\) 为任意一个有限整数集合，则有 \[ \begin{aligned} \sum_{k\in K}ca_k&=c\sum_{k\in K}a_k &(\texttt{分配律}) \\[6pt]\sum_{k\in K}(a_k+b_k) &= \sum_{k\in K}a_k + \sum_{k\in K}b_k &(\texttt{结合律}) \\[6pt]\sum_{k\in K}a_k&=\sum_{p(k)\in K}a_{p(k)} &(\texttt{交换律}) \end{aligned} \] 需要详细解释的是「交换律」。其中 \(p(k)\) 表示一个作用在 \(K\) 上的置换。 或者更为宽松的：对于每个 \(k\) ，有且仅有唯一的 \(p(k)\) 与之对应，且 \(p(k)\in K\)​​ 。 例如 \[ \sum_{k\in K \land k\texttt{是偶数}} a_k = \sum_{n\in K \land n\texttt{是偶数}} a_n = \...

CF1485C Floor and Mod 题解 题目链接：CF1485C Floor and Mod 题意： 多组询问。给定 \(x,y\) ，求 \(1\le a\le x,1\le b\le y\) 且 \(\lfloor\frac{a}{b}\rfloor =a\bmod b\) 的\((a,b)\) 个数。 数据范围： \(1\le Q \le 100,~1 \leq x, y \leq 10^9\) 。 这道题有点麻烦 QAQ 先推一波柿子 \[ \begin{aligned} \left\lfloor{\frac{a}{b}}\right\rfloor &= a \bmod b \\\\\left\lfloor{\frac{a}{b}}\right\rfloor &= a-\left\lfloor{\frac{a}{b}}\right\rfloor\times b \\\\\left\lfloor{\frac{a}{b}}\right\rfloor &=\frac{a}{b+1} \end{aligned} \] 显然 \(b +1 \m...

CF427C Checkposts 题解 题目链接：CF427C Checkposts 题意： 懒得贴翻译，那个翻译太烂了 Your city has $ n $ junctions. There are $ m $ one-way roads between the junctions. As a mayor of the city, you have to ensure the security of all the junctions. To ensure the security, you have to build some police checkposts. Checkposts can only be built in a junction. A checkpost at junction $ i $ can protect junction $ j $ if either $ i=j $ or the police patrol car can go to $ j $ from $ i $ and then come back to $ i $ . Build...

洛谷P2424 约数和 题解 题目链接：P2424 约数和 题意： 对于一个数 \(X\)，函数 \(f(X)\) 表示 \(X\) 所有约数的和。例如：\(f(6)=1+2+3+6=12\)。对于一个 \(X\)，Smart 可以很快的算出 \(f(X)\)。现在的问题是，给定两个正整数 \(X,Y(X<Y)\)，Smart 希望尽快地算出 \(f(X)+f(X+1)+\dots +f(Y)\)的值，你能帮助 Smart 算出这个值吗？ 对于 \(100\%\) 的数据有 \(1\leq X<Y\leq 2\times 10^9\)。 设 \(f(n) = \sum_{i=1}^{n} g(i)\) 其中 \(g(i)\) 表示 \(i\) 的约数个数和 \[ \begin{aligned} f(n) &= \sum_{i=1}^{n} \sum_{j \mid i}^{n} j \end{aligned} \] 变换枚举顺序 \[ \sum_{j=1}^{n}j\sum_{i=1}^{n} [j \mid i] \] 不难发现，\(\sum_{i=1}...

CF1295D Same GCDs 题解 题目链接：CF1295D Same GCDs 题意： 求 \[ \sum_{x=0}^{m-1} [\gcd(a, m) = \gcd(a + x, m)] \] 多组测试数据, \(T \leq 50,\ 1 \leq a < m \leq 10^{10}\) 设 \(p=\gcd(a,m)\) ，则原式可化为 \[ \begin{aligned} \sum_{x=0}^{m-1} [\gcd(a+x,m) = p] &= \sum_{x=0}^{m-1}\left[\gcd\left(\frac{a+x}{p},\frac{m}{p}\right)=1\right] \\\\&=\sum_{x=0}^{m-1}\left[\gcd\left(\left(\frac{a+x}{p} \bmod \frac{m}{p}\right),\frac{m}{p}\right)=1\right] \\\\&= \varphi\left(\frac{m}{p}\right) \end{aligned} \] 即求 ...

模拟赛题讲解[8] 来自 Roundgod 2022-07-27 noi.ac #2681 题目描述： 给定一个有向图 \(G=(V,E)\) ，其中顶点个数 \(\vert V\vert=n\), 边数 \(\vert E\vert=m\)。顶点编号为 \(1-n\) ，边的编号为 \(1-m\) ，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\) 。 对于图中的每个顶点 \(v\) ，你需要判断它属于以下哪种: 如果不存在从 \(1\) 到 \(v\) 的路径，输出 \(0\) 。 如果存在恰好一条从 \(1\) 到 \(v\) 的路径，输出 \(1\) 。 如果存在多于一条且有限的从 \(1\) 到 \(v\) 的路径，输出 \(2\) 。 如果存在无限条从 \(1\) 到 \(v\) 的路径，输出 \(3\) 。 输入格式： 输入第一行包含 \(2\) 个整数 \(n,m\)，分别表示图的顶点数和图的边数。 接下来 \(m\)行，每行包含两个整数 \(a_i,b_i(1\leq a_i,b_i\leq n,a_i\neq b_i)\) ，表示第 \(i\)...

模拟赛题讲解[7] 来自 Roundgod 2022-07-27 noi.ac #2682 题目描述： 给定一个有向图 \(G=(V,E)\) ，其中顶点个数 \(\vert V\vert=n\) ，边数 \(\vert E\vert=m\) 。顶点编号为 \(1-n\) ，边的编号为 \(1-m\) ，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\)。 你最少需要添加多少条有向边，才能使得能够从 \(1\) 到达所有顶点? 输入格式： 输入第一行包含 \(2\)个整数 \(n,m\)，分别表示图的顶点数和图的边数。 接下来 \(m\)行，每行包含两个整数 \(a_i,b_i(1\leq a_i,b_i\leq n,a_i\neq b_i)\) ，表示第 \(i\) 条边从顶点 \(a_i\) 指向顶点 \(b_i\)。 输入保证图中不存在重边和自环。 输出格式： 在一行中输出一个整数，表示最少需要添加的有向边条数。 输入1： 9 9 1 2 1 3 2 3 1 5 5 6 6 1 1 8 9 8 7 1 输出1： 3 输入2： 5 4 1 2 2 3 3 4 4...

模拟赛题讲解[6] 来自 Roundgod 2022-07-27 noi.ac #2683 题目描述： 给定一个连通无向图 \(G=(V,E)\) ，其中顶点个数 \(\vert V\vert=n\) ， 边数 \(\vert E\vert=m\) 。顶点编号为 \(1-n\) ， 边的编号为 \(1-m\) ，第 \(i\)条边连接顶点 \(a_i\) 和 \(b_i\)。输入保证图中不存在重边。 你现在需要对图中的每条边定向: 对于原图中的每条无向边 \((u,v)\)，你需要选择将它变为有向边 \((u,v)\)或者有向边 \((v,u)\). 对于图 \(G\)中的每个顶点 \(v\in V\)，定义 \(r_v\) 为将图定向之后 \(v\) 能够到达的顶点个数，你需要选择一种定向使得最大化 \(\min\limits_{v \in V}r_v\)，也就是最大化所有 \(r_v\) 的 最小值。输出这个最大化的值。 输入格式： 输入第一行包含 \(2\)个整数 \(n,m\)，分别表示图的顶点数和图的边数。 接下来 \(m\)行，每行包含两个整数 \(a_i,b_i(1...

# 洛谷P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G 题解 题目链接：P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G 题意： 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 \(A\) 喜欢 \(B\)，\(B\) 喜欢 \(C\)，那么 \(A\) 也喜欢 \(C\)。牛栏里共有 \(N\) 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。 对于 \(100\%\) 的数据，\(1\le N\le10^4\)，\(1\le M\le5\times 10^4\)。 首先考虑最简单的情况 如果给定的是一个DAG（有向无环图） 当且仅当存在两个及以上出度为 \(0\) 的结点时，答案为 \(0\) （无解） 但是题目给的不一定是DAG 注意到每个强连通分量内的结点两两可达 用这题的语言就是，某个强连通分量内的所有结点可以同时为“明星” 于是考虑强连通分量缩点，接下来就是DAG的情况了 注意此时的...

模拟赛题讲解[5] 来自 Roundgod 2022-07-26 noi.ac #2678 题目描述： 对于任意非负整数 \(x\) 和 \(m(2\le m\le 10)\) ，定义 \(f_m(x)\) 为 \(x\) 在 \(m\) 进制下的各位数字之和。给定两个整数 \(k\) 和 \(m\) 。你需要计算在所有满足是 \(k\) 倍数的正数 \(x\) 中,最小的 \(f_m(x)\) 值是多少。 输入格式： 输入第一行包含两个整数 \(k,m(2\le m\le 10)\) 。 输出格式： 在一行中输出一个整数，表示答案。 输入1： 5 10 输出1： 1 输入2： 79992 10 输出2： 36 输入3： 4 5 输出3： 4 数据范围： 对于 \(30\%\) 的数据，\(1\le k\le 100\) 对于 \(100\%\) 的数据，\(1\le k\le 10^6\) 题解： 尝试以最小的花费构造一个数使得其是 \(k\) 的倍数 如果我们把这个构造的过程放在模 \(k\) 的意义下 问题就转化为了，如何以最小的花费构造一个 \(0\) 设 \(d_x,~...