算法leetcode

力扣372-超级次方

字数统计: 1k字   |   阅读时长: 5分
, , , ,

摘要: 力扣 372：快速幂、扩展欧拉定理

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

题目

你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

提示：

1
2
3
4
1 <= a <= 2^31 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

示例 1：
输入：a = 2, b = [3]
输出：8

示例 2：
输入：a = 2, b = [1,0]
输出：1024

示例 3：
输入：a = 1, b = [4,3,3,8,5,2]
输出：1

示例 4：
输入：a = 2147483647, b = [2,0,0]
输出：1198

题解

算法1：快速幂

用快速幂解决个难题的核心是以下两个公式，按照公式实现即可。

  1. (a * b) % mod = (a % mod) * (b % mod)
  2. $a^{\sum\limits_{i}10^{i}b[i]} = \prod\limits_{i=0}\limits^{n-1}a^{10^{i}b[i]}$

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int superPow(int a, vector<int>& b) {
        // a > 0, b > 0
        int len = b.size();
        int ans = 1;
        a %= M;
        for(int i = len - 1; i >= 0; --i)
        {
            if(b[i] != 0)
                ans = (ans * _power(a, b[i])) % M;
            a = _power10(a);
        }
        return ans;
    }

private:
    const int M = 1337;

    int _power10(int a)
    {
        int n = 10;
        int ans = 1;
        while(n)
        {
            if(n & 1)
                ans = (ans * a) % M;
            a = (a * a) % M;
            n >>= 1;
        }
        return ans;
    }

    int _power(int a, int n)
    {
        int ans = 1;
        while(n)
        {
            if(n & 1)
                ans = (ans * a) % M;
            a = (a * a) % M;
            n >>= 1;
        }
        return ans;
    }
};

算法2：欧拉降幂

欧拉函数

欧拉函数 $\phi(n) :=$ 小于等于 n 且与 n 互质的正整数的个数。

由算是基本定理，可以把 n 写成以下形式：

于是我们可以直接写出 $\phi(n)$ 的计算公式如下，具体推导过程用到容斥原理，参考文章 组合数学4-容斥原理,鸽巢原理。

在欧拉函数 $\phi(n)$ 的基础上，根据同余的理论，我们可以给出欧拉定理和扩展欧拉定理，参考文章 同余。

欧拉定理

下面是欧拉定理的描述，可以用群论证明，参考文章 组合数学5-群论。

若 a, n 为正整数且 a, n 互质，则 $a^{\phi(n)} \equiv 1 \mod n$

因此 $a^{b} \equiv a^{b \mod \phi(n)} \mod n$

扩展欧拉定理

处理 a, n 不一定互质的情况。

若 a, n 为正整数，则

利用扩展欧拉定理的降幂算法

1
2
3
4
当 b >= phi[MOD] 时
    pow(a, b) % MOD = pow(a, (b % phi[MOD]) + phi[MOD]) % MOD
当 b < phi[MOD]
    直接用快速幂(上式仅 b >= phi[MOD] 时成立)

代码 (C++)

get_phi(n) 是用素数筛求欧拉函数的代码模板，详细内容参考 素数筛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
vector<int> get_phi(int n)
{
    if(n < 2) return {};
    vector<bool> vec(n, true);
    vec[0] = false;
    vec[1] = false;
    int cnt = 0;
    vector<int> primes;
    vector<int> phi(n, -1);
    phi[1] = 1;
    for(int i = 2; i < n; ++i)
    {
        if(vec[i])
        {
            ++cnt;
            phi[i] = i - 1; // 性质2
            primes.push_back(i);
        }
        for(int j = 0; j < cnt && i * primes[j] < n; ++j)
        {
            vec[i * primes[j]] = false;
            if(i % primes[j] == 0)
            {
                phi[i * primes[j]] = phi[i] * primes[j]; // 性质4
                break;
            }
            else
                phi[i * primes[j]] = phi[i] * (primes[j] - 1); // 性质1: 积性函数
        }
    }
    return phi;
}

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        const int M = 1337;
        int phi = get_phi(M + 1)[M];
        int numB = b[0]; // 从高位开始
        a = a % M;
        if(a == 0) return 0;
        for(int i = 1; i < (int)b.size(); ++i)
            numB = (numB * 10 + b[i]) % phi;
        numB += phi;
        int x = a;
        for(int j = 0; j < numB; ++j)
        {
            x = x % M;
            x *= a;
        }
        x /= a;
        return x;
    }
};
Share