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."
Разница между en1 и en2, 14 символ(ов) изменены

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↵
            }↵
        }↵
    }↵
~~~~~'

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский spookywooky 2019-02-03 18:07:02 14
en1 Английский spookywooky 2019-02-03 17:50:09 1689 Initial revision (published)