Блог пользователя Lien

calculate 1+a^1+a^2+...+a^d mod m
Автор Lien, 11 лет назад, По-английски

Hi! I'm now thinking about calculate geometric sum: 1+a+a^2+..+a^n mod m where a,m,n are 64-bit integer. I transform 1+a+a^2+...+a^n mod m=(a^(n+1)-1)/(a-1) mod m but a new problem appear: when gcd(a-1,m)>1 it seem impossible to find t such that t*(a-1) mod m=1. Any hint for this problem?

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

You can use the same idea as in binary exponentiation. Just calculate this sum together with an + 1 and you can easily write down formulas for transitions.

→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

S = ( 1+a+a^2+...+a^(sqrt(n)-1) )%m; // sqrt(n) max that sqrt(n)*sqrt(n)<=n

t= (a^sqrt(n))%m;

ans=1;

for(int i=0; i<sqrt(n); i++) ans = ((ans*t)+S)%m;

for(int i=0; i<(n- sqrt(n)*sqrt(n); i++) ((ans*a)+1)%m;

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

It can also be done using matrix exponentiation:

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -17 Проголосовать: не нравится

    This breaks a butterfly upon a wheel.

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Can you give some links to editorials or some books which can help to improve skill of seeing this kind of "matrix patterns"? Or this is just your own experience?

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      I use the following: imagine you have some loop which alters several variables in linear way, for example:

      int a = 1, b = 2, c = 3;
for (int i = 0; i < n; i++) {
  int a1 = a + b - c;
  int b1 = 2 * a + c;
  int c1 = b + 4 * c;
  a = a1;
  b = 1;
  c = c1;
}

      Then let's imagine that we have one row vector instead of three variables. Each iteration of loop alters this vector in some linear way, thus, we can represent one iteration as a matrix:

      After than we can easily simulate any amount of loop's iterations in logarithmic time.

      → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I use almost the same idea as yeputons:
      We have vector
      Lets construct such matrix A that Fn + 1 = AFn.
      Then Fn = AnF0.

      In this case, f1 = an, f2 = S(n):

      In order to better understand this, it is useful to construct such matrices for these sums: , , , , , .
      fib(i) — i-th Fibonacci number.

      → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -14 Проголосовать: не нравится

    seems like we can generalize this formula:

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Looks like you have a problem with modulus arithmetics and division. As far as it is simple to do addition and multiplication in modulus arithmetics, it is not obvious how to do division. Have a look at first comment to this post It says that is modulus is a prime number and you want to calculate (a / x) MOD m you can calculate inverse element inv = x m-2 and then multiply a * inv

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

It's possible to perform the calculation of an + 1 - 1 modulo m * (a - 1) and then perform the division by a - 1. The proof of correctness goes into the Chinese Remainder Theorem.

→ Ответить