Improvement of @ShuangquanLi's solution, with full proof of the math theorem.


  • 0
    A

    The math statement is the following:
    For any positive integer n and a, let phi(n) be the Euler number of n,
    pow(a, n) = pow(a, n-phi(n)) mod n.
    The proof: Let n be equal to the product of n_1, n_2, ..., n_k for each n_i a power of distinct primes p_i. By Chinese Remainder's Theorem, it suffices to show that pow(a, n) and pow(a, n- phi(n)) are equal mod each n_i.
    If a is coprime to n_i, this follows from Euler's theorem a^phi(n_i) = 1 mod n_i and phi(n_i) divides phi(n).
    If a is some power of p_i, I claim both sides are zero mod n_i.
    Consider the inequality r <= 2^(r-1) <= p_i^(r-1) for any positive integer r.
    Suppose n_i = pow(p_i, r), then n >= n - phi(n) >= n_i - phi(n_i) = p_i^(r-1) >= r.
    Let delta = n - phi(n). We rewrite the equality as
    pow(a, delta + phi(n))= pow(a, delta) mod n.
    The conclusion is as long as b is greater than the delta, we can throw away any multiple of phi(n).
    Therefore, the only improvement below is to add phi when the remainder y is less than delta. It doesn't impact the performance much, but theoretically cleaner. The time is under 2ms.

    public class Solution {
        private final int m = 1337;
        private final int phi = 1140;
        private final int delta = m - phi;
        private int myPow(int x, int y) {
            int ret = 1;
            x %= m;
            while (y > 0) {
                if ((y&1) == 1) ret *= x;
                ret %= m;
                y >>= 1;
                x = x*x % m;
            }
            return ret;
        }
         
        
        public int superPow(int a, int[] b) {
            a %= m;
            if (a == 0) return 0;
            int y = 0;
            for (int i : b) y = (y*10 + i) % phi;
            if (y < delta) y += phi;         // make sure the remainder is greater than delta. 
            return myPow(a, y);
        }
    }
    
    • @param a any pos * @param b the power
      • @return pow(a,b) = pow(a,y) mod m
        */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.