CF104021D

进行一个莫比乌斯反的演

大致题意:若一个长度为n的序列,满足gcd为d,且最大的数不超过m,则称其满足条件,若一个序列满足条件,则答案加上(a1a2a3*…)^k,给定n,m,d,k,求答案(mod59964251)

思路:

答案可转化成$\sum_{a_{1}=1}^{m}\sum_{a_{2}=1}^{m}...(a_{1}*a_{2})^{k}*(gcd==d)$

再转化成$\sum_{a_{1}=d}^{m/d}\sum_{a_{2}=d}^{m/d}...(a_{1}*a_{2})^{k}*d^{k}*(gcd==1)$

将$d^{k}$提出来后,变成$d^{nk}$

其中gcd==1可变成$\sum_{ t|a1,t|a2.. .}u(t)$,即mobius函数

此处运用了$\sum_{d\|n}u(d)=1$,当且仅当n=1,否则为0的性质.即t遍历了gcd的所有约数,若gcd为1,则其和为1,否则为0,与原式一致.

将u(t)作为主体,提到前面,可以得到$d^{nk}\sum_{t=1}^{m/d}u(t)\sum_{a1=1}^{m/td}...\sum_{an=1}^{m/td}(a1*a2*a3*a4...)^{k}*t^{k}$

再将t^k提到前面来,得到$d^{nk}\sum_{t=1}^{m/d}t^{nk}*u(t)\sum_{a1=1}^{m/td}...\sum_{an=1}^{m/td}(a1*a2*a3*a4...)^{k}$

这样后面关于ai的遍历就变得十分自由,可以发现该式子可以表示成$(1^{k}+2^{k}+3^{k}+...+m/td^{k})^{n}$的形式,因为将该式子展开后每一项都表示a序列的一种情况对答案的贡献

最终答案的式子已经得到,但需要注意题目中n的范围极大,而题目中n仅作为幂次出现,故需要进行降幂处理,即对任何数c,都存在:

$a^{b}mod c =a^{b mod {\phi(c)}+{\phi(c)} }$,故现将n作为字符串读入,再将其降幂存储,其中$\phi(c)$即为欧拉函数