整除

https://codeforces.com/contest/1933/problem/D 题目大意 给出 $n \ (2 \le n \le 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 10^9$。 问是否存在某种排列使得 $a_1 \mod a_2 \mod a_3 \cdots \mod a_n \neq 0$。 简要题解 假设 $m = \min(a)$ 容易想到 $x < y$ 时 $x \mod y = x$，则如果数组中的最小数 $m$ 唯一，那么我们按顺序排 …

https://codeforces.com/contest/628/problem/B 题目大意 给出一个由 $0 \sim 9$ 字符组成的字符串 $S \ (|S| \le 3 \times 10^5)$。问其有多少个子串对应的数字可以被 $4$ 整除（允许前导零）。 简要题解 分为两种情况 $1$ 位，$2$ 位及以上。对于第二种情况只需要判断最后两位能被 …

https://codeforces.com/contest/792/problem/C 题目大意 用字符串给出一个十进制大整数 $S \ (|S| \le 10^5)$。问最少删掉多少位可以得到一个没有前导零的能被 $3$ 整除的数。输出这个数。 简要题解 允许前导零的话这题非常水，直接 $dp[i][j]$ 表示到第 $i$ 位 $\mod 3$ 为 $j$ 的最多选数数 …

关于 2, 5, 4, 25 这一类比较显然。对于 $x = 2, 5$ 只需数字最后 $1$ 位能被被 $x$ 整除即可。 对于 $x = 4, 25$ 只需数字最后 $2$ 位能被整除即可。 之所以我们可以进行截断，是因为 $10 \equiv 0 \ (\bmod 2\ )$, $10 \equiv 0 \ (\bmod 5\ )$ 而 $100 \equiv 0 \ (\bmod 4\ )$, $100 \equiv 0 \ (\bmod …