372. Super Pow

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8

Example2:

a = 2
b = [1,0]

Result: 1024

介绍关于模运算的几个公式:

1. a^b % 1337 = (a%1337)^b % 1337
2. xy % 1337 = ((x%1337) * (y%1337)) % 1337, 其中xy是一个数字如:45, 98等等

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        if (b.empty())  return 1;

        a %= 1337;
        int last = b.back();
        b.pop_back();
        return (myPow(superPow(a, b), 10) * myPow(a, last)% 1337);
    }
private:
    int myPow(int base, int power){
        int res = 1;
        for(int i = 0; i < power; i++)
            res = base*res % 1337;
        return res;
    }
};

利用数学方法

$$ x^{22} = x^{16} x^4 x^2$$

(22) = (10110)b 迭代过程：从右往左

1. 最低位为0，
2. 为1，此时的基底为basebase, res = x^2
3. 为1，此时的基底为base^4, res *= x^4 ,为x^6
4. 为0，此时的基底为base^8

5. 为1， 此时的基底为base^16, res *= x^16 ,为x^22

   class Solution {
   public:
    int superPow(int a, vector<int>& b) {
        if (b.empty())  return 1;
   
        a %= 1337;
        int last = b.back();
        b.pop_back();
        return (myPow(superPow(a, b), 10) * myPow(a, last)% 1337);
    }
   private:
    int myPow(int base, int power){
        int res = 1;
        while(power > 0){
   
            if(power & 1) res = res*base%1337;
   
            //计算各位置上的数
            base = base*base%1337;
            power >>= 1;
        }
        return res;
    }
   };
   

模运算

基本的模运算

将a和b除以m所得的余数相等记为$$a\equiv b(mod\ n)$$

计算除以m的余数，可以说成是"对m取模"。假设

$$a\equiv c(mod\ m)$$且$$ b\equiv d(mod\ n)$$,那么有如下的算式

$$ a + b \equiv c+d(mod\ m)$$

$$ a - b \equiv c-d(mod\ m)$$

$$ a - b \equiv c-d(mod\ m)$$

我们把对任意的1<x<n都有$$x^n\equiv x(mod n)$$成立的合数n称为Carmichael Number。对于给定的整数n，请判断它是不是Carmichael Number。

typedef long long ll

ll pow_mod(ll x, ll n, ll mod){
  ll res = 1;
  while(n > 0 ){
    if(n&1)
      res = res*x%mod;
    x = x * x% mod;
    n >>= 1;
  }
  return res;
}