题意描述

洛谷链接

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

对于 $100\mathrm{\%}$ 的数据满足：$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{array}{ll}1& n=1\\ 0& \mathrm{\exists }i\in [1,m],c_i>1\\ (-1{)}^m& \mathrm{\forall }i\in [1,m],c_i=1\end{array}$$

形式化地解释一下：

• 当 $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$ ，输出 $xmodM$ ；

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

题意描述

洛谷链接

给你一棵 $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\mathrm{\%}$。现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。

题意描述

HydroOJ 链接

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

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

题目描述

洛谷链接

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

题目保证有解。