主要思路
这转化也真是妙…
首先,我们把 \((-1)^b\) 进行转换。发现转换成跟数论相关:\((-1)^b = 1 – 2(b \bmod 2)\),则可以把这个式子弄一下:
这转化也真是妙…
首先,我们把 \((-1)^b\) 进行转换。发现转换成跟数论相关:\((-1)^b = 1 – 2(b \bmod 2)\),则可以把这个式子弄一下:
优美的神仙操作,爱了爱了。
把原式抄下来:
\[ \begin{equation} \sum_{j = 1}^{n} \gcd(i, j)^c \cdot \text{lcm}(i, j)^d \cdot x_j \equiv b_i \pmod{p} \end{equation} \]
蛮好想。考虑暴力,求完两者之间的\(\gcd\)之后枚举最大的因数即为答案。那么如何加速?我们发现\(gcd\)的最大因素也一定是\(a_1\)的因数之一,所以我们直接预处理\(a_i\)的因数,然后回答询问时直接\(\log n\)枚举即可。