If the starlight never fade

题目链接

题意

定义$f(i)$表示方程${(x+y)}^{i} \equiv {x}^{i} (mod p), 1 \leq x \leq p-1, 1 \leq y \leq m $ 解的数量, $p$为素数。
要求计算$\sum_{i=1}^{p-1}if(i)$。

思路

令$g$为$p$的原根,$x \equiv {g}^{a} (mod p)$, $y \equiv {g}^{b} (mod p)$，那么有

$${ ({g}^{a}+{g}^{b}) }^{i} \equiv {g}^{ai} (mod p)$$ $${(1+{g}^{b-a}) }^{i} \equiv 1 (mod p)$$

注意到$1+{g}^{b-a} > 1$

可以令$1+{g}^{b-a} \equiv {g}^{k} (mod p)$，则有

$${g}^{ki} \equiv 1 (mod p).$$ $$ki \equiv 0 (mod p-1).$$ $$k= \frac{s \times (p-1)}{i}$$ $$k= \frac{t \times (p-1)}{gcd(i, p-1)}$$

因为$k$不能取0，所以$k$有$gcd(i,p-1)-1$种取值，逆推上去，$f(i)=m (gcd(i, p-1)-1).$

$$\sum_{i=1}^{p-1}if(i) = \sum_{i=1}^{p-1}i m (gcd(i,p-1)-1)$$ $$= m \sum_{i=1}^{p-1}igcd(i,p-1) - m \frac{(p-1)p}{2}$$ $$S_{1} = m \sum_{d|(p-1)}^{p-1}{d}^{2} \sum_{e=1}^{ \frac{p-1}{d}}e[gcd(e, \frac{p-1}{d}) == 1]$$ $$= m \sum_{d|(p-1)}^{p-1}{d}^{2} \frac{ \frac{(p-1)}{d} \varphi(\frac{(p-1)}{d})}{2}.$$