determinism's blog

Sum of Increasing Powers of a Number
By determinism, 9 years ago, In English

There are 3 numbers: T, N, M. 1 ≤ T, M ≤ 109, 1 ≤ N ≤ 1018 .

What is asked in the problem is to compute . Obviously, O(N) or O(M) solutions wouldn't work because of 1 second time limit. What can I do?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

You should in parallel count Tn and , like in binary exponentiation. It's a small exercise to realize how it should work :)

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

    I just saw this page. By using that formula I can solve it in O(logN), but I couldn't understand what you meant. Can you elaborate a little?

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

      The main idea is that 1 + T + ... + T2n - 1 = (1 + Tn)·(1 + T + ... + Tn - 1). So, knowing the values of and , we can calculate the desired value. To find sum up to 2n, simply take 1 + T·(1 + T + ... + T2n - 1). So, the algorithm is quite the same as binary exponentiation, but you should keep two values during each step.

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

        I understand it now, thanks for a great explanation.

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

      T1 + ... + T2N = (TN + 1)(T1 + ... + TN)

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

        shouldn't it be (T ^ (N + 1) + 1)( T ^ 1 + ... + T ^ n)? UPD: i was wrong

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

          nope, notice that there is no T^2n+1 in the summation.

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

            Sorry, I didn't notice that there T^1, not T^0

            → Reply
»
9 years ago, # |
  Vote: I like it +32 Vote: I do not like it

A more straightforward solution is based on the sum of geometric series : calculate TN + 1 - 1 modulo (T - 1)M with binary exponentiation and divide the remainder by T - 1.

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

    You could not do it if gcd(T - 1, M) ≠ 1. There is a way to avoid this, counting which powers of prime divisors of M numbers TN + 1 - 1 and T - 1 are divisible by, but it's too complicated.

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

      I think it will work. Note that I calculate the numerator modulo (T-1)M, not modulo M.

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

        Oh, sorry, you are right. But if T and M were up to 1018 (maybe this information would be useful for the topicstarter), there would be problems, which we can avoid in the first solution, using binary multiplication.

        And in this solution we should also use binary multiplication, since T·M could be up to 1018. So the complexity is a little worse.

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

    I also thought about it a moment ago, but then I've realized problem states that T - 1 and M are not necessarily relatively prime.

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

      Assume that TN + 1 - 1 = k(T - 1)M + r, r is the remainder modulo (T - 1)M. Because T - 1 divides left-hand side, it must divide the right-hand side: r = (T - 1)r'. We obtain , i.e. r' is the remainder modulo M.

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

    do we need bignum? (T — 1)M can be up to 1e18 — 1e9

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

      Yeah, Kostroma mentioned above that this would require a 'Russian peasant' modular multiplication.

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

        thanks for the info

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

        I read wikipedia's Russian peasant multipication so the overall complexity would be O(lg^2 n) right?

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

slycelote was faster :(

→ Reply
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

f(n) = f(n - 1) * t + 1

→ Reply