### Bellala's blog

By Bellala, history, 6 weeks ago, 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 Comments (1)
 » It's actually a quite fancy trick IMO. I tried to explain as detailed as I can:Let $x$ denote $\prod{(c_j + 1)}$. We know that $A = c_i \cdot x$ is always even since both $c_i$ and $c_i + 1$ are present in that product (exactly one is even). So, $\frac{A}{2}$ is an integer. (We already knew it because it must be even somehow but I wanted to clarify this part also.)Let's denote $p-1$ by $m$ for convenience. We want to find the remainder of $\frac{A}{2}$ divided by $m$, that is, the non-negative integer $r < m$ such that $\frac{A}{2} = km + r$ where $k$ is an integer.We can multiply both sides by $2$ to obtain $A = k \cdot 2m + 2r$. So, if we can obtain a number congruent to $A \bmod 2m$, it is going to be even (as both $A$ and $2m$ are even).Notice that $A' = c_i \cdot (x \ \% \ 2m)$ is congruent to $A \bmod 2m$, so, $A'$ can also be written as $A' = k' \cdot 2m + 2r$, which indicates that $\frac{A'}{2} = k'm + r$. As a result, it is safe to divide $A'$ by $2$ and then take $\frac{A'}{2}\bmod m$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.90846205,"math_prob":0.99995744,"size":1497,"snap":"2022-27-2022-33","text_gpt3_token_len":478,"char_repetition_ratio":0.10247823,"word_repetition_ratio":0.007490637,"special_character_ratio":0.3974616,"punctuation_ratio":0.08580858,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000048,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,4,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-17T04:50:27Z\",\"WARC-Record-ID\":\"<urn:uuid:18208ed5-67dc-4967-ac1d-315d513cd077>\",\"Content-Length\":\"86549\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:7ae98c78-0ebb-4605-a045-c924bb695622>\",\"WARC-Concurrent-To\":\"<urn:uuid:792874ae-1aba-4da4-a7ff-1a8e19a981dc>\",\"WARC-IP-Address\":\"213.248.110.126\",\"WARC-Target-URI\":\"https://codeforces.com/blog/entry/104591\",\"WARC-Payload-Digest\":\"sha1:QETBAZFAUKFLUR3Y66C6TP6JU37DDHYD\",\"WARC-Block-Digest\":\"sha1:RY7TA4RNVOXBRKUQ4HEUD5XPBEPMNSIA\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882572833.95_warc_CC-MAIN-20220817032054-20220817062054-00459.warc.gz\"}"}