I know you on leetcode

For a composite , let p = spf(i) and i = p * m. Then i^i = (p * m)^i = p^i * m^i = p^i * (m^m)^p So once m^m is ready, I only need p^i and (m^m)^p. I process p from large to small. This is valid because if p = spf(i), then all prime factors of m are at least p, so spf(m) >= p. Therefore m^m has either been computed in an earlier stage, or earlier in the same stage. For primes, I compute p^p directly, but with short addition chains instead of binary exponentiation. For composites with the same smallest prime factor p, I keep a running value of p^i and move it forward using the gaps between consecutive valid numbers. This avoids recomputing p^i every time. I also do not initialize all A[i] = i. I only build the prime values and small gap values that are actually needed. Finally, I use one power-of-two index as a temporary cell and restore it at the end, since s^s can be rebuilt by repeated squaring. These tricks bring the number of operations under 5N.

https://wiki.algo.is/Hall's%20marriage%20theorem?utm_source