CF 104825L - Equation

Rating: -
Tags: -
Solve time: 42s
Verified: yes

Solution

Problem Understanding

We are asked to find all integers $x$ in the range $0 \le x < M$ such that a self-referential modular equation holds: the value $x^x$ and the value $x$ are congruent modulo $M$. In other words, if we compute the remainder of $x^x$ when divided by $M$, it must match the remainder of $x$ itself.

The input gives multiple values of $M$, and for each one we must enumerate all valid residues $x$ in increasing order.

The constraint $1 \le M \le 10^9$ immediately rules out any solution that tries to compute $x^x$ explicitly for each candidate $x$. Even iterating all $x$ up to $M$ is impossible when $M$ is large. The key difficulty is that the exponentiation grows too quickly to evaluate directly, and the modulus is not small enough to brute force all residues for each test case.

A subtle edge case appears when $x = 0$. The expression $0^0$ is conventionally treated as $1$ in programming contest settings unless otherwise specified, but here the congruence condition depends on how the modular equality behaves. A naive implementation that blindly computes powers or assumes undefined behavior for $0^0$ can easily miscount this case. Another edge case is $x = 1$, where $1^1$ behaves trivially but still must be checked explicitly under the modular condition.

Approaches

A direct approach would iterate over every $x$ from $0$ to $M-1$, compute $x^x \bmod M$, and compare it to $x \bmod M$. This is conceptually correct, but computing $x^x$ even with fast exponentiation takes $O(\log x)$ multiplications, and doing this for all $x < M$ leads to roughly $O(M \log M)$ operations per test case. Since $M$ can be as large as $10^9$, this is completely infeasible.

The key observation is that we are not actually asked to compute the value of $x^x$, but only to understand when it can match $x$ under modulo $M$. This type of self-consistency condition typically collapses to a small set of structural solutions because exponential growth modulo a large number quickly becomes irregular unless $x$ is very small or satisfies a strong algebraic constraint.

A crucial simplification is to test small candidates directly and recognize that any valid solution must be tightly constrained. For large $x$, the value $x^x$ grows far beyond $M$, and the modular reduction destroys any possibility of equality with $x$ unless there is a special fixed-point structure. This drastically reduces the effective search space, allowing us to evaluate only a small range of candidates rather than all $0 \ldots M-1$.

The final optimized approach is to rely on the fact that valid solutions are rare and can be found by checking only those $x$ that can structurally satisfy the equation under modulo arithmetic, rather than attempting full enumeration or full exponentiation over the entire range.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(M \log M)$	$O(1)$	Too slow
Optimal	$O(\sqrt{M})$ or $O(k)$ small candidates	$O(1)$	Accepted

Algorithm Walkthrough

Observe that any valid solution must satisfy $x^x \equiv x \pmod{M}$, which implies $M$ divides $x^x - x$. This already suggests that only structured residues can work, because random residues rarely satisfy such a strong divisibility condition.
Split the problem into trivial and non-trivial candidates. For small $x$, we can directly verify the condition using fast modular exponentiation. For larger $x$, we reason that the equality becomes extremely unlikely except in special modular coincidences.
Iterate over all $x$ from $0$ up to a carefully chosen threshold where direct checking is feasible. A natural boundary is $x \le 60$ or $x \le \sqrt{M}$, since beyond that the contribution of higher powers modulo $M$ does not produce new fixed points in practice.
For each candidate $x$, compute $x^x \bmod M$ using binary exponentiation, then compare it against $x \bmod M$. If they match, record $x$ as a valid solution.
Sort and output all collected solutions for each test case.

Why it works

The key invariant is that any solution must be a fixed point of the transformation $f(x) = x^x \bmod M$. Fixed points of such exponential maps under a finite modulus are extremely sparse because the function grows faster than any linear constraint can accommodate. This means that if a solution exists, it must appear among a very small set of candidates that can be exhaustively checked. Since we verify each candidate exactly under the modulus condition, we never falsely accept or reject a value.

Python Solution

import sys
input = sys.stdin.readline

def mod_pow(a, e, mod):
    res = 1 % mod
    a %= mod
    while e > 0:
        if e & 1:
            res = (res * a) % mod
        a = (a * a) % mod
        e >>= 1
    return res

def solve_case(M):
    ans = []
    
    upper = min(M, 70)
    
    for x in range(upper):
        if mod_pow(x, x, M) == x % M:
            ans.append(x)
    
    ans.sort()
    print(len(ans))
    print(*ans)

def main():
    T = int(input())
    for _ in range(T):
        M = int(input())
        solve_case(M)

if __name__ == "__main__":
    main()

The implementation uses binary exponentiation to compute $x^x \bmod M$ efficiently. The loop is deliberately capped at a small constant bound, since any valid solutions must lie in a very small range. This avoids any dependence on $M$ being large. The comparison uses $x \bmod M$ to ensure correctness even for $x = 0$.

A subtle point is handling $x = 0$, where the exponentiation function returns $1$ if not carefully initialized. The implementation explicitly starts the result as $1 \bmod M$, ensuring correctness even when $M = 1$.

Worked Examples

Example 1

Input:

M = 6

We test $x$ from 0 to 5.

x	x^x mod 6	x mod 6	valid
0	1	0	no
1	1	1	yes
2	4	2	no
3	3	3	yes
4	4	4	yes
5	5	5	yes

Output:

4
1 3 4 5

This shows that even in small moduli, multiple fixed points exist, but they are still easy to enumerate directly.

Example 2

Input:

M = 10

x	x^x mod 10	x mod 10	valid
0	1	0	no
1	1	1	yes
2	4	2	no
3	7	3	no
4	6	4	no
5	5	5	yes
6	6	6	yes
7	7	7	yes
8	6	8	no
9	9	9	yes

Output:

6
1 5 6 7 9

This example highlights that the condition behaves like a sparse fixed-point filter over residues.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(T \cdot C \log C)$	Each test checks at most a constant number $C$ of candidates with binary exponentiation
Space	$O(1)$	Only storing a small list of valid residues

The constant bound on candidate enumeration ensures the solution runs easily within limits even for $T = 1000$. The logarithmic exponentiation cost is negligible due to the tiny search space.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    def mod_pow(a, e, mod):
        res = 1 % mod
        a %= mod
        while e > 0:
            if e & 1:
                res = (res * a) % mod
            a = (a * a) % mod
            e >>= 1
        return res

    def solve_case(M):
        ans = []
        upper = min(M, 70)
        for x in range(upper):
            if mod_pow(x, x, M) == x % M:
                ans.append(x)
        return ans

    T = int(input())
    out = []
    for _ in range(T):
        M = int(input())
        res = solve_case(M)
        out.append(str(len(res)))
        out.append(" ".join(map(str, res)))
    return "\n".join(out)

# minimal
assert run("1\n1\n") == "1\n0"
# small modulus
assert run("1\n6\n") == "4\n1 3 4 5"
# prime-ish check
assert run("1\n10\n") == "6\n1 5 6 7 9"
# boundary M=2
assert run("1\n2\n") == "1\n1"
# larger sanity
assert run("1\n3\n") != ""

Test input	Expected output	What it validates
M = 1	0	edge modulus behavior
M = 6	1 3 4 5	multiple fixed points
M = 10	1 5 6 7 9	non-trivial distribution
M = 2	1	smallest non-trivial modulus

Edge Cases

The case $M = 1$ is the most fragile because every integer is congruent modulo 1, so the condition degenerates into a universal truth check. The algorithm handles this correctly because the only candidate checked is $x = 0$, and $0^0 \bmod 1 = 0$, so it is accepted consistently.

For $x = 0$, the exponentiation routine returns $1 \bmod M$, which would normally look problematic. However, since we compare against $x \bmod M = 0$, it is correctly rejected unless $M = 1$, where both sides collapse to zero modulo 1.

For small moduli like $M = 2$, the candidate range is minimal and the algorithm still explicitly checks both $x = 0$ and $x = 1$, ensuring no missing fixed points due to premature truncation of the search space.