1 题意

在第 $i$ 天，如果 $\gcd(a,b) = m - i + 1$，那么 $a,b$ 之间会建立一条边

给定 $a,b$，求 $a,b$ 最早什么时候连通

多组询问，离线

$1 \leq n ,q \leq 10^5, 1 \leq m \leq n, 1 \leq a, b \leq n$

$n,m,q,a,b \in \mathbb{Z}$

1 题目大意

给定 $2^n$ 个整数，从 $1$ 到 $2^n$ 编号

给定 $p_{i,j}(1\leq i \leq n, 1 \leq j \leq n)$

定义一次操作为

选中 $2k$ 和 $2k+1$ ( $0 \leq k, k \in Z, 2k+1 \leq n$ ) 其中有 $p_{2k,2k+1}$ 的概率选中 $2k$ 其中有 $p_{2k+1,2k}$ 的概率选中 $2k+1$

把所有选择的数字组成一个新的数列，大小为 $\frac{n}{2}$

显然最后会只剩 $1$ 个数字

问剩哪个数字的概率最大

题意

题目链接: https://atcoder.jp/contests/arc084/tasks/arc084_b

要求 $x = ak(a \in N)$，定义 $f(x)$ 为 $x$ 在十进制下每一位数字的和

思路

一开始肯定想的是大力枚举，但是很快就可以发现大力枚举可以被卡掉，因为另一个数字可以非常大

然后就考虑缩小另一个数字的范围

一开始的思路顺着质因数分解走的，但是想了半天没有想出来

考后发现顺着质因数的过于复杂，我们可以直接考虑 $x \bmod k$ 意义下的情况

从 $x$ 到 $x + 1$，答案显然增加 1

但是如果 x 一直加 1 会加到 10 ，这个情况答案在事实上没有增加 1

我们可以发现只有其在某一步变成 10 倍才会发生这种事件，那么再加一条边

从 $x$ 到 $10x$，答案不增加

这样就构成了一条图，从 $0$ 到 $1$ 的最短路就是所求答案

题意

题目链接: https://loj.ac/problem/2789

给定 $m$ 和一个长度为 $n$ 数列 $a$

一种方案为从 $a$ 中选择 $k (0 \leq k \leq n)$ 个数字出来（在一个方案中，每一位只能选择一次）

一种合法的方案为选择的所有数字加起来不超过 $m$

$n \leq 40$

即 Codeforces Round 1397 比赛链接: https://codeforces.com/contest/1397

A Juggling Letters

题目大意

给你 $n$ 个字符串，问能不能打乱成相等的三个字符串

思路

因为可以随意打乱，所以统计每个字母个数，只要每个字母的个数模 $n$ 余 $0$ 即可