Boring_Day's blog

By Boring_Day, history, 2 years ago, In English

hey i want to calculate something i needed some attention so i wrote must read blog.

let's say i want to calculate a*b % P where 0<= a,b <= 1e9 and p = 1e9+7

how to calculate this by using only integer number i don't want to use long long as many stupid people do.

  • Vote: I like it
  • -50
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Weird that you call people that use long long stupid, but you can solve it in $$$O(\log(\min(a, b))$$$ using only addition with binary "exponentiation". The operator here that is to be applied repeatedly is addition instead of multiplication.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    I am not the only one many people suggest to not use long long because it causes MLE/TLE in many problems.

    Btw Where is the code?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      But don't you think it is unnecessary to use a much more complex algorithm to do such a simple problem and use more time?

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 3   Vote: I like it -7 Vote: I do not like it

        Sometimes i get TLE/MLE that's why i am asking.

        You newbies do not practice problems that's why you don't know.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 2   Vote: I like it +7 Vote: I do not like it

          But, $$$O(\log(\min(a,b)))>O(1)$$$

          Spoiler
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            Rev. 2   Vote: I like it -7 Vote: I do not like it

            Still solves MLE problem. And % Operations on long long is not O(1) i bileave

            Spoiler
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              You are right, it isn't $$$O(1)$$$. But it is still faster. And you want to write a bunch of code instead of a*b%p.

              Spoiler

              By your rating, you can write the code yourself.

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

                I can save it in my code snippets. I have brain

                Give me code why r u wasting my time?

                Spoiler

                Lol i dont know that's why i have written a blog

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                  Rev. 3   Vote: I like it +2 Vote: I do not like it
                  Spoiler

                  Now, guess my rating.

                  You said you will guess.

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

      MLE happens only when you store too many 64-bit integers in a data structure, or use too many 64 bit-integers in a recursive function (which contributes to stack size). The argument that they cause TLE is more or less outdated since most judges have 64-bit architecture now and the main culprit behind the TLE was slow 64-bit multiplication on 32-bit machines.

      If you use the algorithm I suggested on 32-bit machines, it will be slower than 64-bit multiplication. I would have recommended you to write code for this idea yourself, but if you haven't seen binary exponentiation before, you can go through this.

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

        i am getting too many compilation errors like

        Spoiler
        code
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This will compile only with C++20. Try custom invocation on Codeforces.

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

            ok i found my answer on google code works now Thanks

            But can you explain or is there any blog which explains this code. i think i need to learn more about c++ 20.

            nor

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I would recommend reading on binary exponentiation from the article I linked and trying to implement it yourself. If $$$f$$$ is any associative function, calling the function apply_n(a, n, f, base) computes f(base, f(a, f(a, ...))) where a is repeated n times.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    On a serious note, how does this perform compared to Barrett reduction/Montgomery reduction?

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

      Pretty bad, won't recommend.