G - Power Pair Editorial by en_translator
If \(x=0\), only \(y=0\) satisfies the conditions. Also, \(y=0\) is satisfied only if \(x=0\).
Hereinafter, we assume \(1\leq x, y \leq P-1\).
Also, let \(r\) be the primitive root modulo \(P\).
What is primitive root?
\(r\) is said to be a primitive root modulo \(P\) if the minimum integer \(e\) such that \(r^e \equiv 1 \pmod{P}\) is \(P-1\).
In this problem, we use the following property.
\(r^1, r^2, \dots , r^{P-1} \pmod{P}\) is pairwise distinct
\(r^{P-1} \equiv 1 \pmod{P}\)
For a prime \(P\), a primitive root always exists.
You may never have heard of “primitive root,” but the idea is also used in AGC, so we recommend you remember the concept.
For \(1 \leq a,b \leq P-1\), if \(x \equiv r^a, y \equiv r^b \pmod{P}\), then \(x\) and \(a\), and \(y\) and \(b\) corresponds one-by-one.
We have the following transformation.
\(x^n \equiv y \pmod{P}\)
\(\Leftrightarrow\) \(r^{an} \equiv r^{b} \pmod{P}\)
\(\Leftrightarrow\) \(an \equiv b \pmod {P-1}\)
Therefore, the problem boils down to counting the number of pairs \((a, b)\) such that there exists a positive integer \(n\) satisfying \(an \equiv b \pmod {P-1}\).
This number is written as
\(\sum_{a=1}^{P-1} \frac{P-1}{gcd(P-1, a)}\),
but this computation requires an \(O(P)\) time.
To optimize, we factor out the summation with \(g=gcd(P-1, a)\):
\(\sum_{g} \frac{P-1}{g} \times f(g)\),
where \(f(g)\) denotes the number of \(a\) such that \(1 \leq a \leq P-1\) and \(g=gcd(P-1,a)\).
The number of possible \(g\) is at most the number of divisors of \(P-1\). Denoting by \(d\) the number of divisors of \(P-1\), \(f(g)\) can be computed in the decreasing order of \(g\) in a total of \(O(d^2)\) time.
Therefore, this problem has been solved in a total of \(O(\sqrt{P} + d^2)\) time.
The maximum highly composite number less than \(10^{12}\) is \(963761198400 =2^6*3^4*5^2*7*11*13*17*19*23\), which has \(6720\) divisors, so this is fast enough.
posted:
last update: