kazuya's blog

Modulo of GP Sum ?
By kazuya, 4 years ago, In English

Let mod be $$$10^9 + 9$$$. I want to calculate X % mod where $$$ X = ((a/b)^ n -1 )/(a/b - 1)$$$. I know inverse modulo of number N with respect to mod is $$$N^{mod-2}$$$. Also $$$n$$$ is very large so I cannot iterate and add the sum by each term ( I cannot sum the terms $$$1 + (a/b)^1 + (a/b)^2 .. (a/b)^{n-1} $$$). Please help, I was trying to solve this problem. 963A - Знакопеременная сумма

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the issue?? Handle the case where a = b separately and note that 10^9+9 is prime number so write (a/b) as a*b^(-1) modulo N, N = 10^9+9....Where are you facing problem??

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can apply the same technique that is used for binary exponentiation.

Even case: $$$a^0 + a^1 + \ldots + a^{2k - 1} = (a^0 + a^k) \cdot (a^0 + a^1 + \ldots + a^{k - 1})$$$

Odd case: $$$a^0 + a^1 + \ldots + a^{2k - 1} + a^{2k} = (a^0 + a^k) \cdot (a^0 + a^1 + \ldots + a^{k - 1}) \cdot a + 1$$$, where the last $$$1$$$ is just $$$a^0$$$.

In both cases, we reduce finding the sum until $$$2k$$$ or $$$2k + 1$$$ to finding the sum until $$$k$$$.

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

    Can I write $$$X \% mod = ( (t \% mod)^n - 1 ) \% mod * (INVERSE(t - 1 , mod-2) \% mod) ) \% mod $$$ , where $$$ t = ( (a \% mod) * ( INVERSE(b, mod-2) \% mod) ) \% mod $$$ ?

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

      Of course you can write all you want, but to make it work as expected, you better understand it.

      In the current version, inverse with a mod - 2 argument looks suspicious. You may have a powMod (value, power[, mod]). You may also have a inverse (value[, mod]) which might be a shorthand for powMod (value, mod - 2[, mod]). Do figure out what that mod - 2 means there before proceeding.

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

        [deleted] a,b are less than $$$10^9$$$. I will try the Binary Exponentiation method you mentioned.

        → Reply