Q779’s Blog

hdu4135 Co-prime 题解 题目链接：hdu4135 Co-prime 题意： \(T\) 组数据，每组给出 \(a,b,n\) ，求区间 \([a,b]\) 中有多少个数与 \(n\) 互质。 Given a number \(N\), you are asked to count the number of integers between \(A\) and \(B\) inclusive which are relatively prime to \(N\). Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than \(1\) or, equivalently, if their greatest common divisor is \(1\). The number \(1\) is relatively prime to every integer. \(1 \le a\le b\le 10^{...

OI数学总结-组合数学 施工中，咕咕咕…. 排列组合 更多详见 小蓝书 16.1 下面两个指的是无重复的排列与组合 排列数 从 \(n\) 个不同元素中取 \(k(k\le n)\) 个不同元素，并按一定顺序排成一列的方案数 \[ \mathrm{A}_{n}^{k} = \frac{n!}{(n-k)!} \] 也可写作 \(\mathrm{P}_{n}^{k}\) 或直接用组合数写法 \(k! \times \binom{n}{k}\) 代码求解 \(O(n)\) 计算 例如求解 \(A_{n-m+1}^{m} \bmod p\) int res=1; for(int i=n-m+1; i>=n-2*m+2; i--) res=res*i%p; cout << res << '\n' 组合数 从 \(n\) 个不同元素中取 \(k(k \le n)\) 个不同元素的方案数 \[ \binom{n}{k} = \dfrac{n!}{k!(n-k)!} \] 高中一般记作 \(\mathrm{C}_n^{k}\) ，不是很推荐使用。 特别地，规定当...

CF1000D Yet Another Problem On a Subsequence 题解 题目链接：CF1000D Yet Another Problem On a Subsequence 题意： 如果一个数组 \([a_1,a_2,a_3,...,a_n]a_1=n-1\) 并且 \(a_1>0\) ，这个数组就被叫为好数组，如果一个序列能正好分为多个好数组，ta就被叫为好序列，现在给定一个序列，求这个序列有多少好子序列，答案对 \(998244353\) 取模。 The sequence of integers $ a_1, a_2, , a_k $ is called a good array if $ a_1 = k - 1 $ and $ a_1 > 0 $ . For example, the sequences $ [3, -1, 44, 0], [1, -99] $ are good arrays, and the sequences $ [3, 7, 8], [2, 5, 4, 1], [0] $ — are not. A sequence ...

ABC210E Ring MST 题解 题目链接：ABC210E Ring MST 题意：给定一张 \(n\) 个点的无向图，顶点的编号为 \(0,1,\dots,n−1\) 。同时给出两个长度为 \(m\) 的数组 \(a_1,a_2,\dots,a_m\) 和 \(b_1,b_2,\dots,b_m\) 。初始时图中并没有任何边，你可以按照以下操作加边: 选择一个 \(1\le i\le m\) 和一个 \(0<x<n\) ，并在顶点 \(x\) 和顶点 \((x+a_i) \bmod n\) 中添加一条长度为 \(b_i\) 的边。 你现在想要知道，你添加的边的长度总和至少为多少，才能使得整个图连通?如果无论如何都不能使整个图连通，输出 \(−1\) 。 数据范围： \(1 \le a_i < n \le 10^9,~1 \le m \le 10^5,1\le b_i \le 10^9\) 首先我们可以想到把 \((x,(x+a_i)\bmod n)\) 看作一条边 然后答案就是最小生成树，跑个 \(\text{kruskal}\) 不过这个是 \(O...

数学常数表 常数表 \(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\)...