Can't understand a solution to 615D. Multipliers

Revision en1, by Bellala, 2022-07-06 20:14:12

615D - Multipliers

The way to solve this problem is easy. Just let $$$n=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$$$ ($$$p_i$$$ are pairwise different) then the answer will be

$$$ ans=\prod_{i=1}^k \left(p_i^{1+2+\cdots +c_i}\right) ^ { (c_1+1)\cdots (c_{i-1}+1)(c_{i+1}+1)\cdots (c_k+1) } \mod p \\= \prod_{i=1}^k \left(p_i^{c_i(c_i+1)/2}\right) ^ { (c_1+1)(c_2+1)\cdots (c_{i-1}+1)(c_{i+1}+1)\cdots (c_k+1) \mod p-1} \mod p $$$

There're more than one way to get ans (a simple way is to use prefix product). But today I read a solution which I could not understand:

solution

My only question: why we can keep the factor 2 by mod 2*(mod-1)? Thanks in advance

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Bellala 2022-07-06 20:14:12 1113 Initial revision (published)