| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 44 | 32 | 20 | 64.516% |
Руководство Большой Софтверной Компании решило провести тренинги по тимбилдингу для всех $n$ сотрудников компании. На тренинги отведено два дня, в течение которых участники будут выполнять различные задания командами по $k$ человек. Известно, что количество сотрудников компании делится нацело на $k,ドル таким образом, в каждый из двух дней будет образовано ровно $n / k$ команд по $k$ человек в каждой. В оба дня возможно деление на произвольные команды, в частности, разбиение на команды во второй день может никак не зависеть от разбиения на команды в первый день.
Сейчас организаторы тренингов заняты составлением графика распределения людей по командам в каждый из двух дней. Так как одна из целей тренингов --- увидеть, как сотрудники действуют в одной команде с самыми разными людьми, к распределению по командам имеется естественное требование: количество пар людей, участвующих в тренинге в оба дня в одной и той же команде, должно быть как можно меньше.
Оказалось, что распределить людей требуемым образом --- не такая простая задача, как кажется на первый взгляд. Помогите организаторам тренингов определить минимальное количество пар сотрудников, которые окажутся в одной команде в оба дня.
В единственной строке входных данных находятся два числа $n$ и $k$ (4ドル \leq n \leq 10^9,ドル 2ドル \leq k < n,ドル $n$ делится на $k$) --- количество людей в компании и количество людей в одной команде в оба дня тренинга соответственно.
Выведите минимальное количество пар сотрудников, которые окажутся в одной команде в оба дня тренингов.
9 3
0
8 4
4
Пронумеруем сотрудников компании числами от 1ドル$ до $n$.
В первом тесте из условия можно в первый день разбить людей на тройки как $(2, 4, 9),ドル $(1, 3, 8),ドル $(5, 6, 7),ドル а во второй --- как $(2, 5, 8),ドル $(3, 4, 7)$ и $(1, 6, 9)$. При таком разбиении ни одна пара людей не окажется в одной команде в оба дня.
Во втором тесте из условия можно в первый день разбить людей на две команды как $(1, 3, 5, 7)$ и $(2, 4, 6, 8),ドル а во второй день --- как $(1, 2, 7, 8)$ и $(3, 4, 5, 6)$. Тогда четыре пары людей (1ドル$ и 7ドル,ドル 2ドル$ и 8ドル,ドル 3ドル$ и 5ドル,ドル 4ドル$ и 6ドル$) окажутся в оба дня в одной и той же команде. Можно показать, что решения лучше не существует.