Общая идея


Для каждого теста (набора из $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

Ссылки


Задача
Лекция
Разбор задач