A. B

$[n=1]=\sum \limits_{d|n} \mu(d)$

于是考虑用莫比乌斯函数容斥出题意中的$[gcd=1]$。

设$f_n$表示$gcd$为$n$的倍数的答案。

$g_n$表示$gcd$为$n$的答案。

$g_1=\sum \limits_{i=1}^n\mu(i)f_i$

考虑如何求出$f_i$，即整个序列均选择$i$的倍数。

$n$以内$i$的倍数总共有$\lfloor \frac{n}{i} \rfloor$个。

为了保证单调递增，考虑插板法，即在长度为$k$的序列中插入$\lfloor \frac{n}{i} \rfloor-1$个板，来实现分块递增的效果。

然后发现式子化到这里答案只与$\lfloor \frac{n}{i} \rfloor$有关了，所以直接整除分块套个度教筛就好了。

然后发现$\lfloor \frac{n}{i} \rfloor$可能达到很大的级别，并不能预处理阶乘。

但是明眼人都能看出来，只要将阶乘预处理$n^{\frac{2}{3}}$，对于大的部分暴力就好了。

因为题中保证$k$并不大，可以算出来这个总复杂度是不超过$n^{\frac{2}{3}}$的。

B. B君的回忆

要求$g(g(g(g(g(...g(n)...)))))$。

考虑最简单的情况$g(n)$，直接矩阵快速幂就好了。

对于$g(g(n))$，因为里面的数过大，就不会做了。

然而可以发现这个数列存在循环节，可以证明这个循环节是从（转移矩阵的）首项开始的。

只要求出$g$函数在模$p$意义下的循环节$p'$，就可以使内层的$g(n)$对$p'$取模，也就解决了这个问题。

所以题意是求类菲波那契数列循环节。

打表可以发现这个级别并不大，差不多是与模数同级的。

考虑直接通过$bsgs$处理转移矩阵在模$p$意义下的循环节。

然而这个做法的复杂度有丶高，所以考虑一些性质。

设$f(mod)$表示该转移矩阵在模$mod$意义下的循环节。

对$mod$质因数分解为$\prod_{i=1}^{cnt}p_i^{c_i}$。

对于互质的$f(p_i^{c_i})$，$f(p_j^{c_j})$，有$f(p_i^{c_i}p_j^{c_j})=lcm(f(p_i^{c_i}),f(p_j^{c_j}))$，这个似乎是显然的。

问题转化为求$f(p_i^{c_i})$，根据题解我们知道打表发现$f(p_i^{c_i})=f(p_i)p_i^{c_i-1}$，似乎根据类似欧拉函数的性质理解也是可行的。

所以只要求模质数的循环节，质因数分解，搞一下记忆化就能$AC$了。

C. sanrd

考试的时候大概推出来了式子，但是有一个很重要的技巧没有想到，于是完戏了。

给定数组$a$，常数$c$，要求对于所有的$k \in [0,n]$，$s_k=\sum \limits_{i=0}^{m}c^{2ik}a_i$。

很神的展开办法是将$2ik$转化为$(i+k)^2-i^2-k^2$，原式转化为$s_k=\frac{1}{c^{k^2}}\sum \limits_{i=0}^mc^{(i+k)^2}\frac{a_i}{c^{i^2}}$，

于是原式可以通过将一个多项式翻转，相减为定值的卷积求出。

另外一个技巧是将一个式子$bc^{4k}+dc^{2k}+e$简单的转化为$b(c^{2k}+\frac{d}{2b})^2+e-\frac{d^2}{4b}$。

三项式转化为二项式，可以通过二项式定理展开。

然而需要注意当不保证$b!=0$的情况下，需要加一些特判。

另外，本题实际上为多项式多点求值模板题。

多点求值的思想是对每个要求的值$x_0$，使$A$多项式对多项式$x-x_0$取模，模出的一次项即要求的点值。

证明的方法是：令$F=A/(x-x_0)$，$G=A$%$(x-x_0)$，那么有$F(x-x_0)+G=A$，将$x=x_0$代入可得$G=A$。

一个较快的实现方法是：令要代入的值为$v_i$，当前分治区间为$[l,r]$，求得多项式$B=\prod_{i=l}^{r}(x-v_i)$。

进入分治的过程中使$A$对$B$取模就好了。（当然这里的$B$多项式也要通过分治预处理）

因为$B$是区间内任意一个$x-v_i$的倍数，这样取模的做法显然是正确的。