E - Last 9 Digits Editorial by evima
Prerequisite Knowledge
To solve this problem, you need the following two pieces of prerequisite knowledge:
Modulo of integers: The remainder of dividing \(a\) by \(b\) is denoted as \(a \bmod b\).
Exponentiation by squaring: An algorithm to compute \(a^b \bmod m\) in \(O(\log b)\) time complexity.
Additionally, to understand the proof in this explanation, you need the following two pieces of prerequisite knowledge:
Binomial theorem: \((a+b)^n = {}_n C_0 a^0 b^n + {}_n C_1 a^1 b^{n-1} + \dots + {}_n C_n a^n b^0\) holds.
Euler’s theorem: If \(a\) and \(m\) are coprime (their greatest common divisor is \(1\)), then \(a^{\varphi(m)} \bmod m = 1\). Here, \(\varphi(m)\) is the number of integers among \(1, 2, \dots, m-1\) that are coprime with \(m\).
Both are typical knowledge in competitive programming. If you are not familiar with them, this is a good opportunity to learn them.
There is only one answer
In competitive programming, “experimenting” with sample inputs and other cases can sometimes help grasp properties that lead to a solution.
Let’s consider the case of \(X = 27\) from the input examples. First, when \(n=3\), we have \(n^n \bmod 10^9 = 27\), but it might also be true for other values of \(n\).
To test this, we can write the following Python program. Although it takes tens of minutes to run, it finds that the answers are \(n = 3, 1000000003, 2000000003, \dots\) (Note: Writing the program in C++ would make it run faster).
for n in range(3*10**9):
if pow(n, n, 10**9) == 27:
print(n) # If the remainder of n^n divided by 10^9 is 27, output n
Next, consider the case of \(X = 3\). The remainder of \(n^n\) divided by \(10^9\) is \(3\) when \(n = 595998427, 1595998427, 2595998427, \dots\). At this point, we can make the following conjecture:
Conjecture: Let \(X\) be an integer that is not a multiple of \(2\) or \(5\). Then, \(n^n \bmod 10^9 = X\) when \(n = a, 10^9+a, 2 \cdot10^9+a, \dots\) (where \(a\) is an integer between \(0\) and \(10^9-1\)).
This conjecture is indeed correct. Moreover, this property holds not only for the case of \(10^9\) but also for \(10^k \ (k = 2, 3, 4, \dots)\). This makes it easier to see the solution.
From smaller to larger problems
A technique for solving competitive programming problems is to use the answers to smaller-scale problems to find the answers to larger-scale problems. Let’s try using this.
As an example, consider the case of \(X = 3\).
- Assume we already know that \(n^n \bmod 10^8 = 3\) when \(n = 95998427, 195998427, 295998427, \dots\).
- From the conjecture, \(n^n \bmod 10^9 = 3\) when \(n = a, 10^9+a, 2 \cdot 10^9+a, \dots\), but from the result in 1., \(a\) must be one of the ten possibilities: \(95998427, 195998427, \dots, 995998427\).
- By checking all ten possibilities, we find that \(a = 595998427\).
Thus, for \(k \geq 3\), we can use the answer to the problem for \(10^{k-1}\) to find the answer to the problem for \(10^k\).
Algorithm
The answer to the problem can be found using the following algorithm:
- Find \(n\) such that \(n^n \bmod 10^2 = X \bmod 10^2\) by brute force. Let this answer be \(a_2\).
- In order, for \(k = 3, 4, \dots, 9\), do the following:
- Find \(n\) such that \(n^n \bmod 10^k = X \bmod 10^k\) by brute force among \(n = a_{k-1}, 10^{k-1} + a_{k-1}, \dots, 9 \cdot 10^{k-1} + a_{k-1}\). Let this answer be \(a_k\).
- The answer to the problem is \(a_9\).
Use exponentiation by squaring to compute \(n^n \bmod 10^k\). The time complexity is \(O(L^2)\), where \(L = 9\) is the number of digits.
Proof of the Conjecture
Finally, let’s prove the conjecture used to solve this problem and conclude the explanation.
First, for \(k \geq 2\) and when \(X\) is not a multiple of \(2\) or \(5\), prove that there is exactly one integer \(n\) between \(1\) and \(10^k-1\), which is not a multiple of \(2\) or \(5\), such that \(n^n \bmod 10^k = X\) (★). This can be proven by considering \(k = 2, 3, 4, \dots\) in order, similar to the algorithm.
For \(k = 2\), (★) holds because the remainders of \(1^1, 3^3, 7^7, 9^9, 11^{11}, \dots, 99^{99}\) divided by \(100\) include \(1, 3, 7, 9, 11, \dots, 99\) exactly once each.
For \(k = 3\), consider an integer \(n\) between \(1\) and \(99\) that is not a multiple of \(2\) or \(5\). Consider \((n + 100t)^{n + 100t}\) for \(t = 0, 1, \dots, 9\). Starting from the binomial theorem, we can transform the expression as follows:
\[ \begin{aligned} (n+100t)^{n+100t} & = n^{n+100t} + (n+100t) \cdot n^{n+100t-1} \cdot 100t + \cdots + n^0 \cdot (100t)^{n+100t} \\ & \equiv n^{n+100t} + (n+100t) \cdot n^{n+100t-1} \cdot 100t \pmod{1000} \\ & \equiv n^{n+100t} + n \cdot n^{n+100t-1} \cdot 100t + 100t \cdot n^{n+100t-1} \cdot 100t \pmod{1000} \\ & \equiv n^{n+100t} + n \cdot n^{n+100t-1} \cdot 100t \pmod{1000} \\ & \equiv n^{n+100t} + n^{n+100t} \cdot 100t \pmod{1000} \\ & \equiv \left(n^n + n^n \cdot 100t \right) \cdot (n^{100})^t \pmod{1000} \end{aligned} \]
Here, it holds that \(n^{100} \bmod 1000 = 1\), because the following holds by Euler’s theorem:
- Since \(\varphi(8) = 4\), we have \(n^4 \bmod 8 = 1\), which means \(n^{100} \bmod 8 = 1\)
- Since \(\varphi(125) = 100\), we have \(n^{100} \bmod 125 = 1\)
Therefore, the above equation becomes:
\[(n + 100t)^{n + 100t} \equiv n^n + n^n \cdot 100t \pmod{1000}\]
Here, since \(n^n\) is not a multiple of \(2\) or \(5\), the remainders of \(n^n, (n+100)^{n+100}, \dots, (n+900)^{n+900}\) divided by \(1000\) include \((n^n \bmod 100), (n^n \bmod 100) + 100, \dots, (n^n \bmod 100) + 900\) exactly once each. Therefore, using the fact that (★) holds for \(k = 2\), we can see that (★) also holds for \(k = 3\).
The same proof applies for \(k = 4, 5, 6, \dots\). Thus, (★) holds for any \(k \geq 2\).
To prove the conjecture, it suffices to prove that “\(n^n \bmod 10^k = X\) cannot be a solution when \(n\) is a multiple of \(2\) or \(5\)” and “if \(n = a\) is a solution to \(n^n \bmod 10^k = X\), then \(n = a + 10^k\) is also a solution”. The former is obvious. For the latter, it follows directly from the previous transformations that \((n+100t)^{n+100t} \equiv n^n \pmod{100}\), and it can be similarly seen that \((a+10^k)^{a+10^k} \equiv a^a \pmod{10^k}\).
Sample Solution
A C++ sample implementation is available at https://atcoder.jp/contests/arc172/submissions/50322918.
In Python, the solution can be implemented as follows:
# In Python, the remainder of a^b divided by m can be computed with pow(a, b, m)
# Function to solve the problem
def solve(x):
# Find the last 2 digits of n
for i in range(1, 100):
if pow(i, i, 100) == x % 100:
n = i
# Find the 3rd, 4th, ..., 9th digits of n in order
for i in range(3, 10):
m = 10 ** (i-1)
for j in range(10):
if pow(n+m*j, n+m*j, m*10) == x % (m*10):
n += m * j
break
return n
# Main part
q = int(input())
for _ in range(q):
x = int(input())
print(solve(x))
posted:
last update: