Sum of Increasing Powers of a Number

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

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

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
11 лет назад
26

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

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

Kostroma

11 лет назад, скрыть # |

+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

11 лет назад, скрыть # ^ |

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

11 лет назад, скрыть # ^ |

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

11 лет назад, скрыть # ^ |

I understand it now, thanks for a great explanation.

→ Ответить

ikbal

11 лет назад, скрыть # ^ |

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

→ Ответить

Reyna

11 лет назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

ikbal

11 лет назад, скрыть # ^ |

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

→ Ответить

kinol

11 лет назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

Reyna

11 лет назад, скрыть # ^ |

me neither

→ Ответить

slycelote

11 лет назад, скрыть # |

+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

11 лет назад, скрыть # ^ |

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

11 лет назад, скрыть # ^ |

← Rev. 2 →

+27

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

→ Ответить

Kostroma

11 лет назад, скрыть # ^ |

← 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

11 лет назад, скрыть # ^ |

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

11 лет назад, скрыть # ^ |

+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.