ivanz's blog

Troubles with segtree problem
By ivanz, history, 4 years ago, translation, In English

Hello! Could you please explain to me why my submission 94709653 gets WA4 in the problem 1422F - Boring Queries? In my solution, I just use a segment tree to calculate lcm on the segment of the array. To calculate lcm of numbers a and b I use following fact: lcm(a, b) = a * b / gcd(a, b). Also, I take into account that we calculate lcm by modulo MOD. So lcm(a, b) = (((a * b) % MOD) * solve(gcd(a, b), MOD)) % MOD, where solve(x, m) returns such y that x * y ≡ 1 (mod m). Why it gets WA4? I think the idea is correct and I used verified patterns of segtree and functions loke gcd, lcm and solve (finding an inverse element in the residue ring modulo).

Please help!!!

P.S. sorry for my poor English, I tried to use Grammarly and translator

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

gcd(a, b) % MOD != gcd(a % MOD, b % MOD)

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it -15 Vote: I do not like it

    .

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      Yes but the lcm is not necessarily smaller than MOD.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -23 Vote: I do not like it

        .

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +23 Vote: I do not like it

          solve(gcd(a % MOD, b % MOD), MOD) != solve(gcd(a, b), MOD) % MOD

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it -18 Vote: I do not like it

            .

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +21 Vote: I do not like it

              The most important reason why you can't do this is this: if A divides B, A % MOD doesn't necessarily divide B % MOD. For example, 3 divides 6 but if you take MOD=4 3 doesn't divide 2. That's why operations like gcd and lcm break down when using MOD.

              → Reply