ОЛП МАИ 2019-2020, 1-ый курс. Соревнование 5. Задача G: геометрическая прогрессия
Invite pending
Общая идея
Для каждого теста (набора из $inline$b_1, q, n$inline$ переменных) необходимо найти сумму первых $inline$n$inline$ членов соответствующей геометрической прогрессии по модулю 1000000007. Напоминаю формулу первых $inline$n$inline$ членов геометрической прогрессии: $inline$S_n = \frac{b_1(q^n — 1)}{(q — 1)}$inline$. Так как числа $inline$q$inline$ и $inline$n$inline$ могут быть очень большими, при вычислении степени мы должны брать модуль (на каждом этапе вычисления, а не только в конце), а также из-за большого количества тестов нам не подойдёт линейная сложность вычисления степени — будем использовать бинарное (быстрое), которое справляется за $inline$log_2n$inline$ операций. Далее умножаем на $inline$b_1$inline$.
Если сложение, вычитание, умножение под модулем равносильны:$$display$$a \pm b = r_a + r_b \ (mod\ p) \\ ab = r_ar_b \ (mod\ p)\\$$display$$ — эти формулы легко доказать исходя из определения модуля и разложения числа на целую часть и остаток, то с делением так не проходит и для того, чтобы поделить число на число под модулем нам нужен обратный элемент, который вычисляется (но лишь если модуль есть простое число; к нашему случаю походит) с помощью расширенного алгоритма Евклида (почему так, смотрите лекцию — ссылка в конце поста). Таким образом находим обратный элемент для $inline$q-1$inline$ по модулю 1000000007 и умножаем на число, получившееся на предыдущих шагах, на забывая взять модуль. Ответ получен.
Теперь приступим к коду; если что-то в тексте общей идеи было непонятно, надеюсь, код, который всегда однозначен, разъяснит лучше.
Код
#include <iostream>
using namespace std;
// types
/*
* Чтобы каждый раз не писать long long
*/
typedef long long llong;
// objects
/*
* Объяляем глобальную константу
*/
constexpr llong const MOD = 1000000007;
// functions
/*
* В C++ оператор % вычислет модуль (остаток) в математическом
* смысле лишь для неотрицательных чисел; нам же понадобится
* модуль отрицательных числе (обратный элемент может быть
* отрицательным)
*/
llong mod(llong a, llong b)
{
return (b + a%b) % b;
}
/*
* Расширенный алгоритм Евклида: возвращает НОД,
* записывает в x и y числа, при подстановке которых
* в выражение a*x + b*x = gcd(a,b) получается верное
* уравнение
*/
llong exgcd(llong a, llong b, llong &x, llong &y)
{
if(a == 0)
{
x = 0, y = 1;
return b;
}
llong xx, yy, g;
g = exgcd(b%a, a, xx, yy);
x = yy - xx*(b/a);
y = xx;
return g;
}
/*
* Быстрое возведение в степень, которое имеет логарифмическую
* сложность от степени, в которую необходимо возвести
*/
llong bin_pow(llong a, llong b)
{
llong res = 1;
while(b)
{
if(b % 2)
res = res*a % MOD;
a = a*a % MOD;
b /= 2;
}
return res;
}
// main
int main( int argc, char *argv[] )
{
int t; // количество тестов
scanf("%i", &t); // считываем
/*
* Я люблю стандартную библиотеку ввода-вывода Си,
* и поэтому чаще всего буду использовать её
*/
// solve
/*
* Объявляем необходимые нам переменные:
*/
llong b, q, n, qn, res;
llong x, y;
for(int i = 0; i < t; ++i)
{
/*
* Считываем входные данные,
* обрабатываем исключительные случаи
*/
scanf("%lli%lli%lli", &b, &q, &n);
if(q == 0)
{
printf("%lli\n", b);
continue;
}
if(q == 1)
{
printf("%lli\n", b*n);
continue;
}
// находим q в степени n
qn = bin_pow(q, n);
// находим обратный элемент (он записывается в x) для q-1
exgcd(q-1, MOD, x, y);
// вычисляем результат, не забывая каждй раз брать модуль
res = mod( mod( b*(qn - 1), MOD ) * x, MOD );
// вывод в stdout
printf("%lli\n", res);
}
return 0;
}
// end
Ссылки
Задача
Лекция
Разбор задач