A. B
标签：
莫比乌斯反演+杜教筛
题解：
看到这题面显然是莫比乌斯跑不了了
设$f[i]$代表$gcd$恰好为$i$的方案数
$g[i]$代表$gcd$为$i$的倍数的方案数
即
$$g[i]=sumlimits_{i|d}f[d]$$
$$g[i]=C_{lfloor frac{n}{i} floor +k-1}^{lfloor frac{n}{i} floor -1}$$
莫比乌斯反演一下
$$f[i]=sumlimits_{i|d}mu{frac{d}{i}}*g[d]$$
$mu[i]$可以杜教筛求
组合数大的直接$O(k)$暴力，小的预处理即可
B. B君的回忆
标签：
矩阵乘+$BSGS$找循环节
题解：
考场上想不到矩阵乘吃枣药丸，想推通项公式结果忘了$Fibonacci$怎么推的了
推了一上午现在终于推出来了
其实难点还是在于生成函数和裂项
设$x=sqrt{5},g[k]=frac{1}{x}*((frac{2}{3-x})^k-(frac{2}{3+x})^k)$
$k==1$可以直接矩阵乘
然而$g$数组的增长速度是非常快的,所以$k>1$的情况需要每一层对某个数取模
设在模$p$意义下的循环节为$h$,那么便有
$$T^hequiv I(mod p)$$
设$V=sqrt{p*2+1}$,$h=x*V-y$
那么便可以$BSGS$在$O(V)$的复杂度内求出$h$了
然而$k<=100$所以复杂度还是不够优秀
其实循环节函数$f(x)$有神奇的性质：
$1>(a,b)=1 f(ab)=lcm(f(a),f(b))$
$2>f(p^k)=f(p)*p^{k-1}$