Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2444. Сумма остатков
Комбинаторика, теория ПойаАлгоритм Эвклида
Олимпиадные задачи на русском языке
| 07/04/2019 | Открытые командные соревнования по спортивному программированию "PRIME TIME" (10) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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` – простое число).
Формат вывода
Для каждого тестового случая вывести на отдельной строке
одно целое число – вычисленную сумму.
Пример ввода
3 2 7 2 1 5 5 3 7 10
Пример вывода
6 10 32
