iftekhar's blog

How to Calculate 1+a^1+a^2+...+a^d mod m (using BigMod method)
By iftekhar, history, 4 years ago, In English

How can I solve this using bigmod method?

If the series is 1+a+a^2+a^3+a^4+a^5 then this will be equal to (1+a^2+a^4)+a(1+a^2+a^4). How can I apply bigmod here!

BigMod : This is for calculating the mod of a large number like 2^100 or 10^18.

long long bigmod(long long a, long long b, long long m)
{
    if(b==0) return 1;
    if(b%2==1)
    {
        long long p1 = a%m;
        long long p2 = bigmod(a,b-1,m);
        return (p1*p2)%m;
    }
    if(b%2==0)
    {
        long long h = bigmod(a,b/2,m);
        return (h*h)%m;
    }
}
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +46 Vote: I do not like it

I think BigMod is what I call Binary Exponentiation, lets say $$$w_n = a^0+a^1+a^2\dots a^n$$$, what we will realize is that if $$$n$$$ is even then

$$$w_n = w_{n\over2} + a^{n\over2}\cdot w_{n\over2}$$$

otherwise

$$$ w_n = w_{\lfloor \frac{n}{2} \rfloor} + a^{\lfloor \frac{n}{2} \rfloor}\cdot w_{\lceil \frac{n}{2} \rceil}$$$

, so $w_n$ can be calculated using binary exponentiation.

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

1 + a^1 + a^2 + ... + a^d = ( a^(d+1)-1 ) /( a-1)

Here, you can compute the value of a^(d+1) mod m using bigmod,then subtract 1 from it.And then mutiply this with inverse modulo of (a-1) mod m.

Here a , d and m should be <= 10^18.

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

    And how do you plan to get the inverse if m ain’t prime?

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

      If m is not prime,we can use extended GCD function to find the inverse value.

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

        What if it just plainly doesn't exist like a = 3, m = 4.

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

          Yes,if m and a-1 are not co-prime then maybe we can't use this formula :(

          → Reply