Привет, Codeforces!

Кратко о том, что здесь происходит: сначала мы находим задачку, решаем её формулой включений-исключений, удивляемся возникшей функции Мёбиуса, узнаём об обобщённой формуле обращения Мёбиуса, выводим решение задачи напрямую с помощью неё, а заодно решаем более общую задачу. Если это кажется Вам интересным, то продолжим.

//Вместо картинки
#include <A>
#include <B>
#include <C>
#exclude <AB>
#exclude <AC>
#exclude <BC>
#include <ABC>

Недавно наткнулся на задачу 803F - Coprime Subsequences, в которой требуется найти число таких подпоследовательностей массива, что НОД всех чисел подпоследовательности равен 1. Задача несложная и решается на основе следующих соображений:

1. Число непустых подпоследовательностей массива из k элементов равно 2^k - 1
2. Задачу можно переформулировать так: необходимо отыскать количество подпоследовательностей, для которых не найдется простого числа, делящего все элементы
3. Пусть P — множество простых чисел до 10⁵, а d(x) — число подпоследовательностей, каждый элемент которых кратен x. Если m(x) — число элементов массива, кратных x, то в соответствии с п. 1 имеем d(x) = 2^m(x) - 1
4. Если взаимнопростые p и q делят x, то p·q также делит x.

Скомбинировав вышесказанное и применив принцип включений-исключений получаем, что

считая, что произведение пустого множества равно 1. Итак, мы получили сумму из 2^|P| слагаемых, но большая часть из них не вносит вклада в ответ, т.к. соответствующее произведение превышает 10⁵. Можно непосредственно нагенерить нужные произведения, а можно просто пройтись по [1;10⁵], отбрасывая числа, не являющиеся произведениями простых (например, это можно проверить за логарифм, посчитав наименьший простой делитель в решете). Я воспользовался 2-м вариантом, и у меня получилось такое решение: 33406195

Сдав задачу, я заглянул в разбор, а там

Я посмотрел в код. Посмотрел в разбор. И снова в код. Функция sign(x), возвращающая знак слагаемого, как раз и есть функция Мёбиуса:

int sign(int x) {
	//lp[x] - наименьший простой делитель, а quot[x] - это x / lp[x]
	int prev = -1;
	int sgn = 1;
	for(; x > 1; x = quot[x]) { 
		if (lp[x] == prev) return 0;
		prev = lp[x];
		sgn = -sgn;
	}  
	return sgn;
}

Почему во включениях-исключениях всплыла функция Мёбиуса? Совпадение? Не думаю.

И тут я пошёл читать про функцию Мёбиуса. Я узнал про формулу обращения Мёбиуса, про обобщённую функцию Мёбиуса для частично упорядоченных множеств (под спойлером). Оказалось, что для обобщённой функции Мёбиуса также справедлива формула обращения, и формула включений-исключений является её частным случаем.

Обобщенный Мёбиус (кому лень идти на википедию)

Для множества A c отношением частичного порядка функция Мёбиуса определяется так

Для μ_A(a, b) справедлива формула обращения:

Заметив, что формула ответа напоминает обращение Мёбиуса, я попробовал вывести решение напрямую с помощью него и вот, что получилось.

Рассмотрим множество A = [1;10⁵] c отношением кратности (именно кратности, а не делимости) в качестве отношения порядка, т.е. (строгий вариант ). Например, , а . Пусть g(x) — число подпоследовательностей, НОД которых равен x. Обозначенная ранее величина d(x) выражается суммой g(y) по всем y кратным x, т.е.

Пусть μ_A(x, y) — функция Мёбиуса для A, тогда, применяя обобщенную формулу обращения Мёбиуса, получаем

Тогда ответ на задачу равен

Если показать, что μ_A(x, 1) = μ(x), то мы получим приведенную ранее формулу для ответа на задачу. Покажем это, сведя наш случай к известному, для которого доказан аналогичный результат.

Доказательство

Рассмотрим порядок "делимость" на множестве A = [1;10⁵], обозначив функцию Мёбиуса для него μ'_A(x, y). В работе From Posets to Derangements: An Exploration of the Mobius Inversion Formula показано (стр. 20-22), что μ'_A(1, x) = μ(x). Докажем, что μ_A(x, 1) = μ'_A(1, x).

По определению в случае x = 1 имеем μ_A(1, 1) = μ'_A(1, 1) = 1, а при x > 1

Утверждение 1: для всякого x > 1 верно

Доказательство: , следовательно,

Утверждение 2: для всяких x и верно

Доказательство

Если , то по определению . Заметим, что z кратно y и не равно ему, следовательно z > y. Получается, что значение μ_A(x, y) складывается только из значений μ_A(x, z), z > y, что даёт возможность применить мат. индукцию для доказательства.

Для удобства запишем выражение для μ_A(x, y) в другом виде:

Для наглядности обозначим, чему равно μ_A(x / y, 1) по определению:

Докажем утверждение индукцией по y в нисходящем порядке.

База: μ_A(x, x) = μ_A(1, 1) = 1. Переход: (y < x):

что и требовалось доказать.

Комбинируя утверждения 1 и 2 получаем, что для всякого x > 1 верно:

Теперь докажем основное утверждение тоже по индукции. База верна по определению. Выполним переход:

что и требовалось доказать.

В итоге получаем:

Таким образом, мы получили решение задачи, не прибегая к включениям-исключениям, а применив обобщенную формулу обращения Мёбиуса. В качестве бонуса имеем решение более общей задачи: