送命规律题。当然也可以考虑用 exgcd 的性质，以下是感性理解：
考虑设这个数为\(x \equiv ya {\pmod b}\)，展开就是：
\[ x = ya + kb, k \in [1, b – 1] \]
发现\(k \geq 0\)时都满足，那么反过来取\(-1\)就可以又满足最大又满足不满足条件。
// P3951.cpp
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
unsigned long long a, b, i;
cin >> a >> b;
cout << a * b - a - b;
return 0;
}
这个搜索好骚啊。
首先直接枚举 20 个数来搞初始根。假设我们拿到了\(s\)个根，那么我们还剩下\(n – s\)个，肯定是重根。所以我们考虑直接搜索剩下的\(n – s\)到底是哪个重根。这个复杂度就是\(\Theta(s^{n – s})\)。至于我们怎么验证解的正确性，就是这道题的精髓了：考虑把这组解写成零点式：
\[ \prod_{i = 1}^n (x – a_i) = 0 \]
我们做一个小的多项式乘法展开这个积式，然后与原式的系数进行对比即可。
一眼可以了解到是一道割点题。对于不是割点的情况，那么被计算的点对一定包含此点本身，又因为有序，所以贡献就是\(2(n – 1)\)。如果是割点的话，就比较麻烦，分下面几个来算：
第一个很好算，是\(2(n – 1)\)。第二个，在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积（注意，这里会多计算一遍与点\(u\)的点对，所以我们第一个改成算\(n – 1\)）；第三个，算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。
综合起来就是，对于点\(u\)：
\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]