Sum of Increasing Powers of a Number

→ Обратите внимание

До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
21:29:02
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Sum of Increasing Powers of a Number

Автор 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.