Contest Duration: - (local time) (100 minutes) Back to Home
Official

## Ex - Product Modulo 2 Editorial by en_translator

When $$M$$ is represented as $$M=p_1^{q_1} p_2^{q_2} p_3^{q_3}\ldots$$ with primes $$p_1,p_2,p_3,\ldots$$, the answer for the original problem can be found by solving for each $$(p_1,q_1),(p_2,q_2),(p_3,q_3),\ldots$$ the following problem:

Let $$p$$ be a prime and $$q$$ be a positive integer. How many sequences $$a$$ of length $$K$$ are there that satisfy the following conditions? $$\cdots (*)$$

• For each $$i(1\leq i \leq K)$$, $$0\leq a_i \leq p^q - 1$$;
• $$\displaystyle \prod_{i=1}^{K}a_i \equiv N \pmod {p^q}$$.

and find their product.

we consider $$(*)$$. Let $$F(p,q,K,N)$$ be the answer for $$(*)$$.

When $$N_1$$ and $$N_2$$ has the same $$p$$-adic order, then $$F(p,q,K,N_1)=F(p,q,K,N_2)$$ holds. (This can be proved by induction.)
Therefore, for fixed $$p$$, $$q$$, and $$K$$, there are about $$O(\log_{ p}N)$$ distinct values of $$F(p,q,K,N)$$. Moreover, $$F(p,q,k,n)$$ can be found as a sum of a linear combination of $$F(p,q,k-1,n')$$, so $$(*)$$ can be solved by means of fast matrix exponentiation.

Hence, the problem has been solved.

##### Supplement

Depending on implementation, divisions by $$(p-1)$$ or $$p$$ may occur. Note that this may cause division-by-zero if they are multiples of $$998244353$$.

posted:
last update: