题意描述

洛谷链接

给定 \(N, M\)，求 \(1 \leq x \leq N\)，\(1 \leq y \leq M\) 且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对。

数据范围：\(T = 10^4\)，\(N, M \leq 10^7\)。

题意描述

洛谷链接

对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a \le x \le b\)，\(c \le y \le d\)，且 \(\gcd(x,y) = k\)，\(\gcd(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。

对于 \(100\%\) 的数据满足：\(1 \le n,k \le 5 \times 10^4\)，\(1 \le a \le b \le 5 \times 10^4\)，\(1 \le c \le d \le 5 \times 10^4\)。

莫比乌斯函数

了解莫比乌斯反演前，我们先要了解莫比乌斯函数。记 \(\mu(n)\) 为莫比乌斯函数，\(n\) 可被分解质因数为 \(n = \prod_{i = 1}^{m}{ {p_i}^{c_i} }\) 定义如下：

\[ \mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exists i \in [1, m], c_i > 1 \\ (-1)^m & \forall i \in [1, m], c_i = 1 \\ \end{cases} \]

形式化地解释一下：

• 当 \(n = 1\) 时，\(\mu(n) = 1\)；
• 当 \(n\) 存在至少一个出现次数大于等于两次的质因子时，\(\mu(n) = 0\)；
• 当 \(n\) 的所有质因子仅出现过一次，且 \(n\) 有奇数个质因子时，\(\mu(n) = -1\)；
• 当 \(n\) 的所有质因子仅出现过一次，且 \(n\) 有偶数个质因子时，\(\mu(n) = 1\)。

题意描述

洛谷链接

有一次，HKE 和 LJC 在玩一个游戏。

游戏的规则是这样的：LJC 在纸上写下两个长度均为 \(n\) 的数列 \(a\) 和 \(b\)，两个数列一一对应。HKE 每次可以找两个相邻的数 \(a_i\) 和 \(a_{i + 1}\)，如果它们两个不互质，HKE 可以选择得到 \((b_i + b_{i + 1})\) 分，然后擦掉 \(a\) 和 \(b\) 位置上的第 \(i, i + 1\) 个数，并把两个序列重新按顺序编号。当所有相邻的数互质时，游戏结束。

HKE 想知道他最大得分是多少。

题意描述

洛谷链接

LibreOJ 链接

小豆现在有一个数 \(x\) ，初始值为 \(1\) 。 小豆有 \(Q\) 次操作，操作有两种类型:

• 1 m： \(x = x \times m\) ，输出 \(x \bmod M\) ；

• 2 pos： \(x = x /\) 第 \(pos\) 次操作所乘的数（保证第 \(pos\) 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），输出 \(x\bmod M\) 。

题意描述

洛谷链接

给你一棵 \(n\) 个点的树，点带权，对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。

题意描述

HydroOJ 链接

打开了黑魔法师 Vani 的大门，队员们在迷宫般的路上漫无目的地搜寻着关押 applepi 的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为 \(k\) 的包包。

擂台赛一共有 \(n\) 项挑战，各项挑战依次进行。第 \(i\) 项挑战有一个属性 \(a_i\)，如果 \(a_i \ge 0\)，表示这次挑战成功后可以再获得一个容量为 \(a_i\) 的包包；如果 \(a_i=-1\)，则表示这次挑战成功后可以得到一个大小为 \(1\) 的地图残片。地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把获得的所有的地图残片都带走（没有得到的不用考虑，只需要完成所有 \(n\) 项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。并且他们至少要挑战成功 \(l\) 次才能离开擂台。

队员们一筹莫展之时，善良的守卫者 Nizem 帮忙预估出了每项挑战成功的概率，其中第 \(i\) 项挑战成功的概率为 \(p_i\%\)。现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。

题意描述

HydroOJ 链接

求一个有 \(n\) 的元素的可重数集 \(\{a_i\}\) 的子集的算术和的异或和。

数据范围：\(a_i > 0\)，\(1 < n < 1000\)，\(\sum a_i \le 2000000\)。

题目描述

洛谷链接

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 \(need\) 条白色边的生成树。

题目保证有解。

题意描述

洛谷链接

OI island 是一个非常漂亮的岛屿，自开发以来，到这儿来旅游的人很多。然而，由于该岛屿刚刚开发不久，所以那里的交通情况还是很糟糕。所以，OIER Association 组织成立了，旨在建立 OI island 的交通系统。

OI island 有 \(n\) 个旅游景点，不妨将它们从 \(1\) 到 \(n\) 标号。现在，OIER Association 需要修公路将这些景点连接起来。一条公路连接两个景点。公路有，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花费要大一些。

OIER Association 打算修 \(n-1\) 条公路将这些景点连接起来（使得任意两个景点之间都会有一条路径）。为了保证公路系统的效率， OIER Association 希望在这 \(n-1\) 条公路之中，至少有 \(k\) 条 \((0 \le k \le n-1)\) 一级公路。OIER Association 也不希望为一条公路花费的钱。所以，他们希望在满足上述条件的情况下，花费最多的一条公路的花费尽可能的少。

而你的任务就是，在给定一些可能修建的公路的情况下，选择 \(n-1\) 条公路，满足上面的条件。