Sum of Increasing Powers of a Number

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

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »

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

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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

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

Всё →

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

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Всё →

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

→ Прямой эфир

Детальнее →

Блог пользователя 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.