This goddamn formula

Revision en2, by plagues, 2022-07-03 20:52:52

Hello, Codeforces! We with 74TrAkToR was solving problems and have noticed one super interesting fact.

So, check this out. 801E - Vulnerable Kerbals is very nice problem we had solved. There is interesting solve with DP on a DAG. I won't go into detail, but in the end we had to solve this problem:

You are given an array (a) with n different numbers from 0 to m — 1. You need to create an array (b) (with same length) with (not necessary different) numbers, so if you multiply first i numbers of b and get in by modulo m, you will receive a[i]. It's guaranteed, that we can create such array.

Ok, it's easy to understand, that we must to solve some equations like $$$a \cdot x \equiv b \pmod m $$$.

How to solve it? We wrote 2 similar solutions, but we had one similar mistake, but.... we got AC. I've checked jury solution and.... there is too this idea.

Well, this solution is based on next fact. We can get $$$b \pmod m$$$ by multiplying $$$a$$$ on some $$$x$$$ if and only if $$$gcd(b, m) \vdots gcd(a, m)$$$. Let's find x. Let $$$a' = gcd(a, m)$$$, $$$b' = gcd(b, m)$$$, then $$$p_a = \frac a {a'} $$$, $$$p_b = \frac b {b'} $$$. Easy to realize that $$$p_a$$$ and $$$p_b$$$ are coprime with m, we can get $$${p_a}^{-1} = {p_a}^{\phi(m) - 1} $$$, so our $$$x = \frac {b} {a} = \frac {b'} {a'} \cdot \frac {p_b} {p_a} = \frac {b'} {a'} \cdot p_b \cdot {p_a}^{\phi(m) - 1} $$$. So, wasn't so hard, really? Mmmaybe, but that's not true, because $$$p_b$$$ can be not comprime with $$$m$$$. $$$m = 24$$$, $$$b = 16$$$. $$$b' = 4$$$, $$$p_b=2$$$. Holy... Idk, i can't found some information about it. It's getting AC and author of this problem too use this formula, I think, it's right. But why??? If we use formula $$$x = b \cdot {a}^{\phi(m) - 1} $$$, it's getting WA7. Maybe weak tests.

I also invented right solution: let's solve diophantine equation $$$ax+my=c$$$. ex_gcd can help you, but we must use $$$(x = 0, y = c / gcd)$$$ at the end.

I have observe one thing: all of numbers $$$a$$$ with same $$$gcd(a, m)$$$ have same $$${a}^{\phi(m)}$$$ that have partly same $$$gcd$$$ with $$$m$$$, but all of prime divisors (p) in maximum power (it power that $$$m \vdots p^x$$$, x — maximal), so, $$${a}^{\phi(m)}$$$ may have other prime divisors.

Can you help us? Thank you for advance. It's really shocking, that we pass similar mistake.

Tags math, modular arithmetic, modulo, dp, gcd, exgcd

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English plagues 2022-07-03 21:17:24 5 Tiny change: 'o came up the right' -> 'o came up with the right'
en7 English plagues 2022-07-03 21:14:06 12 Tiny change: ' There is interesting an intere' -> ' There is an intere'
en6 English plagues 2022-07-03 21:12:21 2 Tiny change: '6$. $b' = 4$, $p_b=2$' -> '6$. $b' = 8$, $p_b=2$'
en5 English plagues 2022-07-03 21:11:54 13 Tiny change: 'n\nI also invented the right' -> 'n\nI also came up the right'
en4 English plagues 2022-07-03 21:10:57 3243
en3 English plagues 2022-07-03 21:05:43 19
en2 English plagues 2022-07-03 20:52:52 3 Tiny change: '24$, $b = 8$. $b' = 4' -> '24$, $b = 16$. $b' = 4'
en1 English plagues 2022-07-03 20:40:46 2286 Initial revision (published)