Покупки на Ошском базаре


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На Ошском базаре продают дыни по a сомов и арбузы по b сомов. У Нургуль есть c сомов, и она хочет купить хотя бы одну дыню и хотя бы один арбуз, потратив не больше c сомов. Сколько у неё вариантов покупки? Вариант — это пара чисел (количество дынь, количество арбузов).

Геометрически это количество точек с натуральными координатами (x, y) в треугольнике a·x + b·y ≤ c.

Рисунок

Ответьте на T вопросов.

Входные данные

В первой строке — число T (1 ≤ T ≤ 10⁵). В каждой из следующих T строк — три целых числа a b c (1 ≤ a, b, c ≤ 10⁹).

Выходные данные

Для каждого вопроса выведите количество пар натуральных чисел (x, y) с a·x + b·y ≤ c.

Пример 1

Вход:

3
2 3 12
5 5 9
1 1 1000

Выход:

8
0
499500

Пояснение

При a = 2, b = 3, c = 12 подходят пары (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (3, 1), (3, 2), (4, 1) — восемь вариантов (на рисунке). При c < a + b вариантов нет.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов c ≤ 10⁵.

Подсказка

Сумма Σ_{i=0}^{n−1} ⌊(a·i + b) / m⌋ вычисляется за O(log m) приёмом, похожим на алгоритм Евклида.


Комментарии

Еще нет ни одного комментария.