Sum of Increasing Powers of a Number

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

Автор determinism, 9 лет назад, По-английски

There are 3 numbers: T, N, M. 1 ≤ T, M ≤ 10⁹, 1 ≤ N ≤ 10¹⁸ .

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

determinism
9 лет назад
26

Комментарии (26)

Написать комментарий?

Kostroma

9 лет назад, # |

+10

You should in parallel count Tⁿ and $\text{[math]}$ , like in binary exponentiation. It's a small exercise to realize how it should work :)

→ Ответить

determinism

9 лет назад, # ^ |

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?

→ Ответить

Kostroma

9 лет назад, # ^ |

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

→ Ответить

determinism

9 лет назад, # ^ |

I understand it now, thanks for a great explanation.

→ Ответить

ikbal

9 лет назад, # ^ |

T¹ + ... + T^2N = (T^N + 1)(T¹ + ... + T^N)

→ Ответить

Reyna

9 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

ikbal

9 лет назад, # ^ |

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

→ Ответить

kinol

9 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Reyna

9 лет назад, # ^ |

me neither

→ Ответить

slycelote

9 лет назад, # |

+32

A more straightforward solution is based on the sum of geometric series $\text{[math]}$ : calculate T^N + 1 - 1 modulo (T - 1)M with binary exponentiation and divide the remainder by T - 1.

→ Ответить

Kostroma

9 лет назад, # ^ |

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 T^N + 1 - 1 and T - 1 are divisible by, but it's too complicated.

→ Ответить

slycelote

9 лет назад, # ^ |

← Rev. 2 →

+27

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

→ Ответить

Kostroma

9 лет назад, # ^ |

← Rev. 2 →

+21

Oh, sorry, you are right. But if T and M were up to 10¹⁸ (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 10¹⁸. So the complexity is a little worse.

→ Ответить

determinism

9 лет назад, # ^ |

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.

→ Ответить

slycelote

9 лет назад, # ^ |

+11

Assume that T^N + 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 $\text{[math]}$ , i.e. r' is the remainder modulo M.