Покупки на Ошском базаре
На Ошском базаре продают дыни по 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) приёмом, похожим на алгоритм Евклида.
Комментарии