Задачник Базовый курс EN

Сколько оснований лгут

простые числа теория чисел подсчёт вариантов

Тест Миллера — Рабина ошибается на составном n, только если выбранное основание — сильный лжец. Запишем n − 1 = 2^s·d с нечётным d. Основание a (1 ≤ a ≤ n − 1) — сильный лжец, если a^d ≡ 1 (mod n) или a^2ⁱd ≡ −1 (mod n) для какого-нибудь i от 0 до s − 1. Основание — лжец Ферма, если aⁿ⁻¹ ≡ 1 (mod n).

Чтобы понять, насколько опасно число для теста, хочется знать, сколько у него лжецов того и другого сорта. Перебрать все основания нельзя: числа доходят до 4·10¹⁸. Зато для каждого числа известно его разложение на простые множители.

Например, у 2047 = 23 · 89 сильных лжецов 242 (среди них 1, 2 и 2046), а лжецов Ферма — 484.

Вход

В первой строке число t (1 ≤ t ≤ 10 000). В каждой из следующих t строк описано одно число: сначала количество различных простых делителей k (1 ≤ k ≤ 15), затем k пар «простое p, показатель e» в порядке возрастания p. Число n = ∏ p^e нечётное, составное и меньше 2⁶².

Выход

Для каждого числа — строку из двух чисел: сколько сильных лжецов и сколько лжецов Ферма среди оснований от 1 до n − 1.

Примеры

Пример 1

Вход

5
1 3 2
2 3 1 5 1
3 3 1 11 1 17 1
2 23 1 89 1
3 7 1 19 1 67 1

Выход

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Лжец обязательно взаимно прост с n. По китайской теореме об остатках выбрать основание по модулю n — то же, что выбрать его остаток по модулю каждого p^e независимо. А сравнение по модулю n выполнено, когда оно выполнено по модулю каждого p^e. Сколько решений у a^d ≡ 1 по модулю одного p^e?

2Подсказка 2

Обратимые остатки по модулю p^e (для нечётного простого p) образуют цикл: все они — степени одного остатка g, первообразного корня. Их φ(p^e) = p^e−1(p − 1). В цикле длины m уравнение x^t = 1 имеет ровно gcd(t, m) решений. А x^t = −1?

3Подсказка 3

Случаи «a^d ≡ 1» и «a^2ⁱd ≡ −1» при разных i не пересекаются: после −1 в цепочке идут только единицы. Значит, лжецов можно считать по случаям и складывать.

4Идея

Считаем решения по модулю каждого p^e и перемножаем — это китайская теорема. Пусть p − 1 = 2^s_p·d_p с нечётным d_p. По модулю p^e: у a^d ≡ 1 ровно gcd(d, d_p) решений, у a^2ⁱd ≡ −1 — ровно 2ⁱ·gcd(d, d_p), если i < s_p, и ни одного иначе. Перемножив по всем k простым и сложив случаи, получаем формулу Монье:

$$S(n) = \prod_p \gcd(d, d_p) \cdot \Bigl(1 + \sum_{i=0}^{\nu - 1} 2^{ik}\Bigr), \qquad F(n) = \prod_p \gcd(n - 1, p - 1),$$

где ν — наименьшее из s_p.

5Разбор

Почему решений столько. Пусть g — первообразный корень по модулю p^e, m = φ(p^e), и x = g^y. Тогда x^t = 1 означает m | ty, и подходящих y от 0 до m − 1 ровно gcd(t, m). Остаток −1 — это g^m/2 (единственный остаток порядка 2), и x^t = −1 означает ty ≡ m/2 (mod m). Такое сравнение разрешимо, когда gcd(t, m) делит m/2, и тогда у него тоже gcd(t, m) решений.

Теперь подставим. Число p делит n, значит, не делит n − 1 и d, поэтому gcd(d, m) = gcd(d, d_p) — от множителя p^e−1 и от двоек в m нечётное d ничего не берёт. Для t = 2ⁱd получаем gcd(t, m) = 2^{min(i, s_p)}·gcd(d, d_p), а m/2 содержит двойку в степени s_p − 1. Делимость выполнена ровно при i < s_p. Так же для лжецов Ферма: gcd(n − 1, m) = gcd(n − 1, p − 1).

По китайской теореме основание — лжец, когда нужное сравнение выполнено по модулю каждого p^e, а остатки по разным модулям выбираются независимо. Случай a^d ≡ 1 даёт ∏ gcd(d, d_p) оснований, случай a^2ⁱd ≡ −1 — произведение 2ⁱ·gcd(d, d_p) по всем k простым, то есть 2^ik·∏ gcd(d, d_p), если i меньше всех s_p, и ноль иначе. Складываем случаи i = 0, …, ν − 1.

Проверка на 2047 = 23 · 89: d = 1023, 22 = 2 · 11, 88 = 8 · 11, ν = 1, k = 2. S = 11 · 11 · (1 + 1) = 242, F = gcd(2046, 22) · gcd(2046, 88) = 22 · 22 = 484.

В Go всё помещается в uint64: S и F не больше n, а слагаемые суммы — степени двойки не больше 2^νk ≤ ∏ p ≤ n, потому что каждое p ≥ 2^ν + 1.

5+Решение

6Сложность

На число — k алгоритмов Евклида и вычисление n из разложения: O(k log n). Перебор оснований стоил бы O(n log n) — для n около 10¹⁸ это миллиарды лет.

7Типичные ошибки

Перебор оснований. Верен и годится для проверки на числах до нескольких тысяч, но на больших тестах безнадёжен.
Забытая единица в скобке. Слагаемое 1 — это основания с a^d ≡ 1, например само a = 1. Без него у 15 вышел бы один лжец, а их два: 1 и 14.
Степени простых. Для p^e хочется взять gcd(d, φ(p^e)) — и это правильно, просто множитель p^e−1 с d общих делителей не имеет. А вот gcd(n − 1, p^e − 1) вместо gcd(n − 1, p − 1) уже ошибка.
ν по показателю n − 1. Сумма идёт до наименьшего s_p, а не до s: при i ≥ s_p по модулю этого p^e решений нет.

Алгоритмы задачи

NUM Алгоритм Тест Миллера — Рабина Простота числа за k возведений в степень: основания-свидетели ловят составное, лжецов не больше четверти. O(k log³ n) 2 задачи NUM Алгоритм Китайская теорема об остатках Число по остаткам от нескольких модулей: алгоритм Гарнера и точные вычисления по многим простым. O(k²) операций с машинными числами 2 задачи NUM Алгоритм Алгоритм Евклида Наибольший общий делитель двух чисел за O(log n) делений с остатком. O(log min(a, b)) 2 задачи