| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 34 | 16 | 12 | 63.158% |
В детском саду готовятся к новому году, и воспитательница !A !B !C решила организовать детей, чтобы они подготовили украшения и отправили их Санте Клаусу для украшения своих оленей.
Дети с интересом восприняли идею и вырезали из бумаги $a$ звездочек и $b$ снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте $x$ звездочек и $y$ снежинок, где 0ドル \le x \le a$ и 0ドル \le y \le b$. Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие $x + y > 0$.
Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты $n$ оленей, поэтому если будут отправлены $x$ звездочек и $y$ снежинок, величина $x+y$ должна делиться на $n$.
Воспитательница заинтересовалась: а сколько есть всего различных способов составить посылку Санте Клаусу. Два способа считаются различными, если в них отличается количество звездочек или количество снежинок.
В одном наборе входных данных содержатся несколько тестов. Каждый тест следует решить независимо.
Первая строка входных данных содержит целое число $t$ --- количество тестов (1ドル \le t \le 10^5$).
Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел $n,ドル $a$ и $b$ --- количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (4ドル \le n \le 10^9$; 0ドル \le a, b \le 10^9$).
Выведите $t$ чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $t = 1,ドル $a, b \le 1000$ |
| 2 | 10 | $t \le 1000,ドル $a = 0$ |
| 3 | 15 | $t \le 1000,ドル $a, b < n \le 1000$ |
| 4 | 10 | $t \le 1000,ドル $a, b \le 1000$ |
| 5 | 15 | $t = 1,ドル $n \le 1000$ |
| 6 | 10 | $t \le 1000,ドル $n \le 1000$ |
| 7 | 30 | нет |
4 4 2 2 4 4 4 6 5 5 8 13 17
1 6 5 30
В первом тесте у Санты 4ドル$ оленя, а дети вырезали 2ドル$ звездочки и 2ドル$ снежинки. Здесь подходит только один набор --- нужно отправить все вырезанные украшения.
Во втором тесте у Санты также 4ドル$ оленя, но дети вырезали 4ドル$ звездочки и 4ドル$ снежинки. Здесь подходит 6 наборов: 0 звездочек и 4 снежинки, 1 звездочка и 3 снежинки, 2 звездочки и 2 снежинки, 3 звездочки и 1 снежинка, 4 звездочки и 0 снежинок, а также 4 звездочки и 4 снежинки.
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2022 5번