Description

题目链接：Codeforces 1110C

定义函数 $f(a)$ 的值为：

$$f(a)=\max_{0 <b<a}\gcd(a\oplus b,a\ \&\ b)$$

给出 $q$ 个询问，每个询问为一个整数 $a_i$。你需要对于每个询问，求出 $f(a_i)$ 的值。

数据范围：$1\le q\le 10^3$，$2\le a_i\le 2^{25}-1$

Description

题目链接：Codeforces 1110F

给你一棵带权有根树，根节点为 $1​$，且保证每个点的父亲 $p_i<i​$，其中 $(p_i,i)​$ 的边权为 $w_i​$。这棵树有个性质：如果我们 $\text{DFS}​$ 这棵树，对于每个点都递增枚举儿子节点，每访问到一个节点就记录其编号，那么得到的序列刚好为 $1​$ 到 $n​$。

现在有 $q​$ 次询问，每次给出 $v_i,l_i,r_i​$，求从 $v_i​$ 出发到 $[l_i,r_i]​$ 中的其中一个叶子节点的最短距离（保证 $[l_i,r_i]​$ 中至少有一个叶子节点）。

数据范围：$3\le n\le 5\times 10^5​$，$1\le q\le 5\times 10^5​$，$1\le p_i<i​$，$1\le w_i\le 10^9​$

$\text{Splay}$ 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链。

Description

题目链接：Codeforces 594D

今天的数学课上，老师告诉 Vovochka 正整数的欧拉函数 $\varphi(n)​$ 是计算小于等于 $n​$ 且与 $n​$ 互质的正整数的函数，$1​$ 和任意正整数互质所以 $\varphi(1)=1​$。

现在老师给了 Vovochka 一个数列 $a_1,a_2,\dots,a_n​$，要求回答 $q​$ 个询问 $l_i,r_i​$，计算 $\varphi\left(\prod_{i=l}^r a_i\right)​$ 的值，答案对 $10^9 + 7​$ 取模。这个问题对二年级学生来说太难了，所以你决定帮助 Vovochka。

数据范围：$1\le n,q\le 2\times 10^5​$，$1\le a_i\le 10^6​$

Description

题目链接：Codeforces 900D

求满足下面两个条件的数列 $a_1,a_2,\dots,a_n(1\le a_i)​$ 的个数（答案对 $10^9+7​$ 取模）：

1. $\gcd(a_1,a_2,\dots,a_n)=x$
2. $\sum_{i=1}^n a_i=y​$

数据范围：$1\le x.y\le 10^9​$

Description

题目链接：Codeforces 1102F

给你一个 $n​$ 行 $m​$ 列的矩阵 $a_{i,j}​$，其中每个元素都是正整数 。

你可以任意改变行的顺序，但是不能改变同一行中元素的顺序。确定行的顺序后，你可以通过以下方式遍历整个矩阵：首先访问从顶行到底部的第一列的所有元素，然后对第二列进行相同的操作，依此类推。在遍历期间，按照访问它们的顺序记下元素，得到一个序列 $s_i​$。设这个序列为 $s_1,s_2,\dots,s_{nm}​$。

如果对于任意的 $i(1\le i<nm)​$，有 $\vert s_i-s_{i+1}\vert\ge k​$ 成立，我们称 $k​$ 是合法的。

你要做的是寻找一个 $a_{i,j}$ 的行的排列顺序，使得最大的合法的 $k​$ 值最大。

数据范围：$1\le n\le 16​$，$1\le m\le 10^4​$，$2\le nm​$，$1\le a_{i,j}\le 10^9​$

Description

题目链接：Codeforces 786A

Rick 和 Morty 在玩一个版本的 Berzerk 游戏。这个游戏需要很大的空间，所以他们使用电脑玩这个游戏。

游戏中有 $n​$ 个标号从 $1\sim n​$ 的物体围成一个圆圈（顺时针标号）， 物体 $1​$ 表示黑洞，其它物体表示星球，且某一个星球上有一个怪物，Rick 和 Morty 不知道这个怪物在哪个星球上，只知道这个怪物在游戏开始时没有进入黑洞。但就目前而言，他们希望为每种可能的情况做好准备。

Rick 和 Monty 每人有一个数的集合，集合中的数在 $[1,n-1]$ 之间。Rick 的集合是 $s_1$，其中有 $k_1$ 个数，Morty 的集合是 $s_2$，其中有 $k_2$ 个数。 游戏开始后，两人轮流操作。在操作中，玩家必须从他的集合中选出一个数 $x$， 怪物将从当前位置顺时针移动 $x$ 个位置，如果怪物移动后进入了黑洞，则该玩家获胜。

你的任务是对于每一个怪物的位置以及玩家先后手顺序，判断游戏先手获胜、后手获胜、无限循环。（每个玩家都采取最优操作）

数据范围：$2\le n\le 7000$，$1\le k_1,k_2\le n-1$，$1\le s_{i,j}\le n-1$

Description

题目链接：Codeforces 1034A

Mr. F 现在有 $n$ 个正整数 $a_i$。

他认为这些数的最大公因数太小了，所以他想通过删除其中的一些数来增大这个最大公因数。你的任务是计算出最少的需要删除的数的个数，使得删除之后剩余数的最大公约数大于删除之前的最大公约数。无解输出 $-1$。

数据范围：$2\le n\le 3\times 10^5$，$1\le a_i\le 1.5\times 10^7$

Description

题目链接：Codeforces 776E

Holmes 的孩子们在争论谁才是他们中最聪明的。

Mycroft 提出了如下的函数求值问题：已知 $f(1)=1​$，且当 $n\ge 2​$ 时，$f(n)​$ 表示满足 $x+y=n​$ 的互质的正整数对 $(x,y)​$ 的对数，$g(n)=\sum_{d\mid n}f\left(\frac{n}{d}\right)​$。

她定义了一个函数 $F_k(n)$，其值可以通过如下式子递归求解：

$$F_k(n)=\begin{cases} f(g(n)) & k=1 \\ g(F_{k-1}(n)) & k>1,k\bmod 2=0 \\ f(F_{k-1}(n)) & k>1,k\bmod 2 =1 \end{cases}$$

现在她希望你对于给定 $n,k$，求出 $F_k(n)\bmod 1000000007$ 的值。

数据范围：$1\le n,k\le 10^{12}$

Description

题目链接：BZOJ 4804

求如下式子的值：

$$\sum_{i=1}^n\sum_{j=1}^n\varphi(\gcd(i,j))$$

本题 $T$ 组数据。

数据范围：$1\le T\le 5000$，$1\le n\le 10^7$