Давайте заметим, что у нас могут быть только следующие пары чисел: (x,x), (x,2∗x), (x,3∗x).
Пусть d=gcd(a,b), тогда заметим, что не может быть a=k⋅d, где k>4, так как иначе lcm точно будет не меньше k⋅d>3⋅d. Тогда остается только варианты выше, а также (2⋅d,3⋅d). Но в этом случае lcm=6⋅d.
Количество первого типа n, второго ⌊n2⌋, третьего ⌊n3⌋. А значит ответ на задачу равен n+⌊n2⌋+⌊n3⌋.
Давайте заметим, что ответ на задачу не меньше n2k, так как квадрат можно разбить на непересекающиеся подпрямоугольники размера 1×k. Значит нужно научиться делать пример на это число.
Решим вначале задачу, без ограничения на закрашенную клетку. Тогда нам хочется сделать что-то типа шахматной расскраски, то есть диаганальную раскраску.
В этом случае, мы можем пронумеравать диаганали (от самой "нижней", до самой "верхней"). В этом случае в каждом подпрямоугольнике будет k подряд идущих диагоналей, а значит, если закрасить каждую k диаганаль, то мы получим ответ на задачу (и ответ в точности будет равен n2k, так как в каждом подпрямоугольнике мы закрасили ровно одну клетку).
Ну а можно заметить, что клетка (x,y) принадлежит диагонале с номером x+y. (Так как когда мы идем на одну клетку вверх-влево, то одна из координат увеличивается на 1, а другая не меняется). А значит, нужно просто закрасить все клетки, у которых (x+y)%k=(a+b)%k
Очевидно, что для любого i должно выполняться, что либо ai=bi, либо bi≤bi+1+1, так как либо ai уже равно bi и i элемент увеличивать не нужно, либо же мы должны увеличить ai до bi операциями из условия, а на них накладываются ограничения выше.
Теперь докажем, что этих двух условий достаточно. Пусть i — это индекс минимального элемента в a, который не равен bi. Тогда заметим, что мы в любом случае сможем сделать ai:=ai+1, так как в этом случае выполняется ai≤bi≤bi+1+1, а значит можно увеличить ai. То есть такими операциями можно получить массив b.
Давайте поймем, что задачу можно переформулировать следующим образом: Дано полное бинарное дерево с 2n листами. Также для каждой вершины, не являющейся листом, помечено ребро в ровно одного из детей. А ответ на задачу — это лист, до которого можно добраться из корня по отмеченным ребрам. А изменения — это сменить помеченное ребро выходящее из вершины.
Тогда понятно, что нет смысла делать изменения больше, чем у одной вершины на уровне, так как нам важна только одна вершина, до которой идет путь, а значит ответ зависит только от того, на каких глубинах мы решили поменять исход (и очевидно, что разные множества изменненых исходов дают разного победителя). А значит если k фиксированно — \binom{n}{k} (так как нам нужно просто выбрать, какие из k глубин мы будем изменять), а значит ответ на задачу равен \sum{\binom{n}{i}}, где 0 \leq k \leq min(n, k).
Давайте будем перебирать c, тогда gcd(a, b) = gcd(a, a + b) = gcd(a, n - c). Значит gcd(a, b) являются делителем числа n - c. Давайте тогда переберем все делители числа n - c. Пусть d является делителем, тогда количество пар чисел a, b, где a + b = n - c и gcd(a, b) = d равно \phi (\frac{n - c}{d}), так как нам нужно a кратное d и при этом оно должно быть простым с \frac{n - c}{d}, чтобы gcd был в точности равен d.
А значит ответ на задачу равен \sum{lcm(c, d) * \phi{\frac{n - c}{d}}}, где 1 \leq c \leq n - 2, а d делит n - c