I would appreciate it if someone explains the solution for 102055K - Mr. Panda and Kakin
I tried reading AC solutions, but I could not understand them.
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
I would appreciate it if someone explains the solution for 102055K - Mr. Panda and Kakin
I tried reading AC solutions, but I could not understand them.
Name |
---|
You know that $$$a^{(p - 1)(q - 1)} \equiv 1$$$ $$$mod$$$ $$$pq$$$, from Euler's Theorem. You can now get modular inverse of $$$(2^{30} + 3)$$$ $$$mod$$$ $$$(p - 1)(q - 1)$$$ using extended gcd algorithm. Calculate $$$c^{\frac{1}{2^{30} + 3}} = FLAG$$$, using fast exponential.
Thank you for your answer, however, I want to ask 2 questions:
How did you arrive at the formula that flag = $$$c^{{1}/{2^{30}+3}}$$$
How can we using fast exponentiation here? the value of c*c will overflow 64 bits?
Why did we find the inverse of 2^30 +3 mod (p-1) * (q-1) in particular and not mod n for example ?
$$$a^b$$$ $$$mod$$$ $$$n \equiv a^{b \; mod \; \varphi(n)}$$$ $$$mod$$$ $$$n$$$, from the Euler's Theorem, as $$$a^{\varphi(n)} \equiv 1$$$ $$$mod$$$ $$$n$$$, we can substract multiples of $$$\varphi(n)$$$ from the exponent.
Can you please provide details for the following subroutines used in your approach:
$$$1. \,$$$ Proof for $$$a^{(p - 1)(q - 1)} \equiv 1 \,mod \,pq$$$ given that $$$a$$$, $$$p$$$ are coprime and $$$a$$$, $$$q$$$ are coprime from $$$a^{\phi(n)} \equiv 1 \,mod \,n$$$ (where $$$a$$$ and $$$n$$$ are coprime) $$$i.e.$$$ from Euler's Theorem.
$$$2.$$$ If $$$b^{-1}\,mod\,n$$$ is known then how to evaluate $$$a^{\frac{1}{b}} \,mod\,n$$$.