lox123's blog

By lox123, history, 6 weeks ago, In English

Hello, Codeforces! 74TrAkToR and I were solving problems and have noticed one super interesting fact.

So, check this out. 801E - Vulnerable Kerbals is a very nice problem we have solved. There is an interesting solution 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 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 this idea toox.

Well, this solution is based on the following 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' = 8$$$, $$$p_b=2$$$. Holy... Idk, i can't found some information about it. It's getting AC and the author of this problem uses this formula too, I think, it's right. But why??? If we use formula $$$x = b \cdot {a}^{\phi(m) - 1} $$$, it's getting WA7. Maybe are weak tests.

I also came up with the 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 observed one thing: all of numbers $$$a$$$ with the same $$$gcd(a, m)$$$ have the same $$${a}^{\phi(m)}$$$ that have partly the same $$$gcd$$$ with $$$m$$$, but all of the 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 in advance. It's really shocking, that we pass a similar mistake.

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

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve what exactly? $$$ax \equiv b \pmod m$$$? It's equivalent to the Diophantine equation $$$ax - mk = b$$$, which is classically solved with extended Euclidean algorithm. Also, you may find solution explicitly as

$$$ x \equiv \frac{b}{g} \left(\frac{a}{g}\right)^{-1} \pmod{\frac{m}{g}}, $$$

where $$$g = \gcd(a, m)$$$, granted that $$$b$$$ is divisible by $$$g$$$. If it's not divisible, there are no solutions. Also see here.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, we know that, thank you! But we don't know why our and author's solutions too works. So, exgcd too can solve straightaway $$$a \cdot x \equiv b \pmod m $$$ if you do one уeasy change (I've described in post), it will be more easy to write.

    Spoiler
    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      As I see, your formula rewrites in my terms as

      $$$ x \equiv \frac{b}{g} \left(\frac{a}{g}\right)^{\phi(m)-1} \pmod m. $$$

      I think it follows from the representation of $$$x$$$ modulo $$$\frac{m}{g}$$$, as $$$\phi(\frac{m}{g})$$$ divides $$$\phi(m)$$$.

      In other words, it is because

      $$$ \left(\frac{a}{g}\right)^{-1} \equiv \left(\frac{a}{g}\right)^{\phi(\frac{m}{g})-1} \equiv \left(\frac{a}{g}\right)^{\phi(m)-1} \pmod{\frac{m}{g}}. $$$
      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I too think it's related, we were thinking about it, but we where is the correlation with powers?

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Correlation of which powers with what?

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            Oh, i'd understand! Thank you a lot! You're right.

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

i think here is mistake with $$$b'$$$

$$$m=24,b=8,b'=gcd(8,24)=8$$$

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I mean you have written $$$b'=4$$$, but with your definition $$$b'=gcd(b,m)$$$ it's wrong

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Yeah, b = 16, fixed. Thank you!

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$b'$$$ should be fixed too $$$gcd(24,16)=8$$$

»
6 weeks ago, # |
  Vote: I like it +105 Vote: I do not like it

I found that every comment in this blog has the number of upvotes being a multiple of 8.