Ладно бы только на Тимусе, у нас четвертьфинал с такими условиями :(

Да ладно, по-моему вполне нормальные условия были.

Это оригинальные условия с контеста были. Впрочем да, у уральцев всегда так.

По поводу H:

Будет построено a² + b² зданий и 4(a + b) участков забора. Условие, что можно разбить означает, что gcd(a² + b², 4(a + b)) ≠ 1

Все b одной четности подойдут. Иначе, a+b нечетно, тогда это равно gcd(ab, a + b). Поймем, что это не 1, тогда и только тогда gcd(a, b) ≠ 1. В одну сторону очевидно. Пусть p — общий простой делитель ab и a + b. Тогда или a или b делится на p. Но так как , то и второе тоже делится на p.

Утверждается, что это сводится просто к количеству меньших, с общим делителем, если что-то на что-то поделить. Я уже точно не помню.

Это считается так: . Вроде какая-то очевидная формула включений-исключений. Все делители вместе с μ находятся перебором, после того, как разложили.