【题解】2021年牛客寒假集训营第一场题解
【题解】2021年牛客寒假集训营第二场题解
【题解】2021年牛客寒假集训营第三场题解
幂塔个位数的计算
思路：使用拓展欧拉定理进行欧拉降幂。降幂的思路是每次向下递归会使得 p ′ = ϕ ( p ) p'=\phi(p) p′=ϕ(p) ，最多递归 log n \log n logn 层。注意写法，推荐H的写法，重载快速幂中的乘法，用来保证返回的指数满足公式。
教程：扩展欧拉定理
H代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50175693
红和蓝
思路：树上点两两配对，典中典思路。
AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68626333
牛牛与整除分块
思路：发现 ∀ 1 ≤ i ≤ n , ⌊ n i ⌋ \forall 1\leq i\leq \sqrt n, \left \lfloor \frac n i \right\rfloor ∀1≤i≤n,⌊in⌋ 两两不同。
AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68641390
牛牛与牛妹的RMQ
思路：每次找到区间内的最大值作为分割，然后分治。
AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68634848
牛牛与字符串border
思路： ∀ i ∈ [ 0 , n ) \forall i\in[0, n) ∀i∈[0,n) 都有 i ↔ ( i + k ) m o d n i\leftrightarrow(i+k)\bmod n i↔(i+k)modn 之间连边 ，那么形成一个长度为 gcd ( n , k ) \gcd(n, k) gcd(n,k) 的循环节。
对于这道题，不完全按照这个结论。
AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68634897
模数的世界
思路：容易猜到最大 gcd \gcd gcd 为 p − 1 p-1 p−1 ，即求 k 1 , k 2 k_1, k_2 k1,k2 满足 p − 1 ∣ a + k 1 × p p-1|a+k_1\times p p−1∣a+k1×p 且 p − 1 ∣ b + k 2 × p p-1|b+k_2\times p p−1∣b+k2×p 使得两两互质，容易知道 k 1 = ( p − 1 − a ) + t 1 × p , k 2 = ( p − 1 − b ) + t 2 × p ( t 1 , t 2 ≥ 0 ) k_1=(p-1-a)+t_1\times p, k_2=(p-1-b)+t_2\times p(t_1, t_2\geq 0) k1=(p−1−a)+t1×p,k2=(p−1−b)+t2×p(t1,t2≥0) 。然后暴力枚举 t 1 , t 2 t_1, t_2 t1,t2 之中的一个，大概是枚举常数个就可以得到互质对。
AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68680579
