C++ 9ms solution, improved by Fermat's Little Theorem


  • 1

    First, 1337 = 7 * 191.
    According to Fermat's Little Theorem, a ^ 6 ≡ 1 (mod 7), a ^ 190 ≡ 1 (mod 191),
    so a ^ lcm(6,190) ≡ 1 (mod 1337), i.e., a ^ 570 ≡ 1 (mod 1337).
    Then, a ^ b ≡ a ^ (b % 570) (mod 1337).

    class Solution {
    public:
        int superPow(int a, vector<int>& b) {
            if(a % 1337 == 0) return 0;
            
            a %= 1337;
            
            int exp = 0, size = b.size();
            for(int i = 0; i < size; ++i) {   // exp = b % 570
                exp = (exp * 10 + b[i]) % 570;
            }
            
            return powModL(a, exp, 1337);
        }
        
        int powMod(int a, int k, int m) {    // a ^ k % m, 0<= k <= 10
            int res = 1;
            while(k-- > 0) {
                res = res * a % m;
            }
            return res;
        }
        
        int powModL(int a, int k, int m) {  // a ^ k % m, for large k
            if(k == 0) return 1;
            return powMod( powModL(a, k / 10, m), 10, m ) * powMod( a, k % 10, m ) % m;
        }
    };
    

Log in to reply
 

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