Обмеження невеликі: k \le 10^5, тому місяць можна просто промоделювати по днях.
Для кожного дня від до послідовно перевіряємо три правила умови саме в такому порядку:
якщо ділиться на , Петрик відпочиває незалежно ні від чого — переходимо до наступного дня;
інакше з'ясовуємо, чи робочий це день за графіком. Цикл графіка має довжину a + b, причому перші днів циклу — робочі. Місяць починається з першого робочого дня, тому день є робочим тоді й лише тоді, коли (d - 1) \bmod (a + b) < a;
якщо день робочий, додаємо до відповіді , коли ділиться на , і в інших випадках.
Порядок перевірок принциповий: правило «кожен -й день» сильніше за графік, а подвійна ефективність застосовується лише до дня, який залишився робочим.
Ключова деталь — це (d - 1) \bmod (a+b), а не d \bmod (a+b): нумерація днів починається з одиниці, а перший день має бути початком циклу.
Складність — . Відповідь може сягати 2k = 2 \cdot 10^5, тож переповнення не загрожує, але 64-бітний тип не завадить.