ABC335 G - Discrete Logarithm Problems

Competitive Programming C++

2024-01-12

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc335/tasks/abc335_g

원문 링크
https://atcoder.jp/contests/abc335/editorial/9017

먼저 \(O(\sqrt{P})\)의 시간을 들여 \(P - 1\)을 소인수분해하여 \(P - 1 = \prod_{k = 1}^n p_k^{e_k}\)라고 합시다.

\(1 \leq x < P\)에 대해, \(x^m = 1 \bmod P\)를 만족하는 가장 작은 양의 정수 \(m\)을(\((\mathbb{Z}/P\mathbb{Z})^*\)에서)위수(位数)라고 합니다. 임의의 \(x\)의 위수는 \(P - 1\)의 약수가 됩니다.

증명
\(x\)의 위수를 \(m\)이라고 하고, \(d = \gcd(m, P - 1)\)이라고 합시다.
확장 유클리드 호제법으로부터 어떤 정수 \(a, b\)가 존재해서 \(am + b(P - 1) = d\)가 됩니다.
페르마의 소정리에 의해 \(x^{P - 1} \equiv 1\)이므로, \(x^d = x^{am+b(P-1)} = (x^m)^a(x^{P-1})^{-b} \equiv 1\)이 되며, 위수의 최소성으로부터 \(d \geq m\)이 됩니다.
한편으로, 최대공약수의 성질로부터 \(d \mid m\)이므로 \(d = m\)이며, \(d \mid P - 1\)이므로 \(m \mid P - 1\)입니다.

이로부터 임의의 \(x\)에 대해 그 위수는 다음과 같은 과정으로 구할 수 있습니다.

• \(M\)을 \(P - 1\)로 둔다
• \(k = 1, 2, …, n\)의 순서로 이하의 과정을 반복한다
  • \(p_k \mid M\)이고 \(x^{M \over p_k} = 1 \bmod p\)인 동안 \(M\)을 \(M \over p_k\)로 바꾸기를 반복한다
• 모든 과정이 종료되는 시점에 \(M\)은 \(x\)의 위수가 된다

반복 횟수는 모두 합쳐 \(\sum\nolimits_i e_i = O(\log P)\)번이며, 각 반복에 있어 판정에 \(O(\log P)\)의 시간이 걸리므로, 이 과정은 \(O((\log P)^2)\)의 시간이 소요됩니다.

\(B_i\)를 \(A_i\)의 위수라고 합시다. 이 때 다음의 2가지 조건을 만족하게 됩니다:

• 어떤 양의 정수 \(k\)에 대해, \(A_i^k = A_j \bmod P\)
• \(B_j \mid B_i\)

증명
\(mod P\)에서의 원시근 \(g\)를 임의로 하나 정해 고정합니다.

보제1: \(g^e\)의 위수는 \((P - 1) \over \gcd(P - 1, e)\)이다.
증명: \(g^e\)의 위수를 \(o\), \(\gcd(P - 1, e)\)를 \(d\)라고 합시다.
위수의 정의로부터 \(o\)는 \((g^e)^o \equiv 1 \bmod P\)를 만족하는 가장 작은 음이 아닌 정수이며, 원시근의 정의로부터 이 조건은 \(eo \equiv 0 \bmod P - 1\)과 동치이므로 \(eo = LCM(e, P - 1)\)이 됩니다. \((P - 1)e = \gcd(e, P - 1)LCM(e, P - 1)\)이므로, \(do = P - 1\)이 되어 증명됩니다.

보제2: 「어떤 음이 아닌 정수 \(k\)에 대해 ((g^{e_1} \equiv g^{e_2} \bmod P)\)이다」(1)와 「\(\gcd(e_1, P - 1) \mid \gcd(e_2, P - 1)\)을 만족한다」(2)는 동치이다.
증명: 전자의 조건은 \(e_1k \equiv e_2 \bmod P - 1\)인 \(k\)가 존재하는 것과 동치이므로 이 조건으로 생각합니다.
(1)\(\Rightarrow\)(2)
대우를 증명합니다. \(gcd(e_1, P - 1)\)일 때, \(gcd(P - 1,e)\)의 약수 \(d\)에 대해, \(\gcd(e_2, P - 1)\)의 약수가 아닌 것이 존재한다. 이 \(d\)에 대해 임의의 \(k\)로 \(e_2 \not\equiv 0 \equiv e_1k \bmod d\)가 성립하며, 이는 mod를 \(d\)의 배수인 \(P - 1\)로 바꾸어도 성립합니다.
(2)\(\Rightarrow\)(1)
\(d_i = gcd(e_i, P - 1), e_i’ = e_i \over d_i\)라고 할 때, \(e_1k \equiv e_2 \bmode P - 1\)인 \(k\)가 존재함을 보이면 됩니다. 양변을 \(d_1\)로 나눠, \(e_1’k \equiv e_2’\frac{d_2}{d_1}\bmod \frac{P - 1}{d_1}\)이 됩니다. \(e_1’\)은 그 정의로부터 \(P - 1\)과 마찬가지로 소수이므로 \(e_1’^{-1} \bmod \frac{P - 1}{d_1}\)가 존재하며 \(k \equiv e_1’^{-1}e_2’\frac{d_2}{d_1}\)를 만족하는 임의의 음이 아닌 정수 \(k\) 가 조건을 만족합니다.

보제3: \(x \mid z, y \mid z\)에 대해 \(x \mid y\)인 것과 \(\frac{z}{y} \mid \frac{z}{x}\)인 것은 동치이다
증명: 생략

원래 주장의 증명:
\(B_i’\)를 \(A_i \equiv g^{B_i’} \bmod P\)를 최소로 하는 음이 아닌 정수라고 합시다. 「어떤 음이 아닌 정수 \(k\)에 대해 \(A_i^k \equiv A_j \bmod P\)이다」인 것은 보제2로부터 「\(\gcd(B_i’, P - 1) \mid \gcd(B_j’, P - 1)\)을 만족한다」와 동치입니다. 이는 보제3에 의해 \(\frac{P - 1}{\gcd(B_j’, P - 1)} \mid \frac{P - 1}{\gcd(B_i’, P - 1)}\)인 것과 동치가 되어 \(B_j \mid B_i\)와 동치가 됩니다.

따라서, 각 \(B_i\)를 실제로 구하는 것으로 문제는 다음과 같이 변형됩니다.

문제(★): \(P - 1\)의 약수인 \(N\)개의 정수 \(B_1, …, B_N\)이 주어진다. \(1 \leq i, j \leq N\)을 만족하는 정수의 쌍 \((i, j)\)이면서, \(B_j \mid B_i\)인 것의 개수를 구하라.

\(B_i\)의 값은 어느 것이든 \(P - 1\)의 약수인 것으로부터, (\(i\)가 아닌)\(B_i\)마다 나누어 떨어지는 조건을 일일히 확인하는 것으로, 문제(★)는 \(\Theta((P - 1의\ 약수의\ 개수)^2)\)의 시간에 푸는 것이 가능합니다.
제약 조건 하에서는 \(P - 1 = 6746328388800,9092877393600\)일 때, \(P - 1\)의 약수의 수는 최대 \(10080\)개이기 때문에 대부분의 언어로 AC를 받을 수 있습니다.

문제(★)를 해결하는 것보다 더 빠른 풀이도 존재합니다.
\(B_i = \prod_{k = 1}^n p_k^{e_{i,k}}\)라고 하면, \(B_j \mid B_i\)인 것은 모든 \(k\)에서 \(e_{j, k} \leq e_{i, k}\)를 만족하는 것과 동치입니다.
따라서 고속 제타 변환(Sum over Subsets DP)을 생각해보면, \(i\)마다 \(B_j \mid B_i\)인 \(j\)의 개수를 구할 수 있습니다(이해하기 어렵다면 \(P = 13, 37, 109\)등의 간단한 케이스를 생각해봅시다).
계산량은 \(O(n * (P - 1의\ 약수의\ 개수))\)가 되고 \(n = O(\log P / \log \log P)\)입니다.
위수를 구하는 과정에 있어서 \(M\)을 소인수분해된 형태와 같이 관리하는 것으로 \(e_{i, k}\)는 추가 계산 없이 구할 수 있습니다.

이산수학이라니

사실 문과인 나로써는 이해하기도 힘든 범위다…

어떻게 해석은 했다만 머릿속에 박히진 않는다. 그냥 증명만 보고 따라하는게 고작일 듯.
보통 F까지만 레이팅 반영이니 다행이려나.

번역하기조차 만만치 않았다.