Still don't get the "You should compute P⋅Q−1 modulo 109+7, where Q−1 denotes the multiplicative inverse of Q modulo 109+7."

Revision en1, by spookywooky, 2019-02-03 17:50:09

Working with fractions usually we get a hint like "You should compute P⋅Q−1 modulo 109+7, where Q−1 denotes the multiplicative inverse of Q modulo 109+7."

So, I more (or less) understood what that means. I can express, say 1/5 by the number 400000003. I can calculate that number using https://www.geeksforgeeks.org/fermats-little-theorem/ implemented by some code I found somewhere (see below).

BUT: How do I add (and/or multiply) fractions with huge values?

i.e. how to calculate and express something like this: Let E=10e9+7 Then, how to express: ((E+1) / (E+2)) + ((E+3) / (E+4))

Any hint or link to an understandable explenation would be really helpfull. Thanks.

The code I use so far, based on that fermat thing: ~~~~~ class Inv { companion object { val defaultMod = 1000000007L var MOD = defaultMod

fun toPower(a: Long, p: Long, mod: Long = MOD): Long {
            var a = a
            var p = p
            var res = 1L
            while (p != 0L) {
                if (p and 1 == 1L)
                    res = res * a % mod
                p = p shr 1
                a = a * a % mod
            }
            return res
        }

        fun inv(x: Long, mod: Long = MOD): Long {
            return toPower(x, mod - 2)
        }

        fun simpleInf(nenner: Long, zaehler: Long): Long {
            return nenner * Inv.inv(zaehler) % Inv.MOD
        }
    }
}

~~~~~

Tags mod, inverse

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English spookywooky 2019-02-03 18:07:02 14
en1 English spookywooky 2019-02-03 17:50:09 1689 Initial revision (published)