Bellala's blog

Can't understand a solution to 615D. Multipliers
By Bellala, history, 2 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$.

→ Reply