06/04/2025 18:15:10

Рабочее место участника

Задачи

2444. Сумма остатков

Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Доктору Манхэттену нужно вычислить сумму

$sum_(i=1)^n\ ((p*i)\ mod\ q)$ , где

$q$ – простое число, для некоторых значений

$p$ ,

$q$ и

$n$ .

Напишите программу, вычисляющую эту сумму для нескольких наборов параметров.

Формат ввода

Первая строка ввода содержит одно целое число

$T$ (

$1\ ≤\ T\ ≤\ 100000$ ) – количество тестовых случаев. Далее следует

$T$ строк, каждая строка содержит три целых числа

$p$ ,

$q$ и

$n$ (

$1≤\ p,\ q,\ n\ ≤\ 10^6$ ,

$q$ – простое число).

Формат вывода

Для каждого тестового случая вывести на отдельной строке одно целое число – вычисленную сумму.

Пример ввода

Пример вывода

6
10
32

Источник: North American IPC 2019