Skip to content

14258: 【原4258】快速幂

题目

题目描述

author: Guo Linsong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4258

Description

给定快速幂算法的思想,要求实现该算法,计算出\(a^n(mod~2019)\)。

快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个快速计算\(a^n\)的小技巧。计算\(a\)的\(n\) 次方可以将\(n\)个\(a\)乘在一起,然而当\(n\)太大的时侯,这种方法就不太适用了。不过我们知道:\(a^{b+c}=a^b\times a^c,a^{2b}=(a^b)^2\)。二进制取幂的想法是,我们将取幂的任务按照指数的 二进制表示来分割成更小的任务。首先我们将\(n\)表示为\(2\)进制,举一个例子:

\(3^{13}=3^{(1101)_2}=3^8\times 3^4 \times 3^1\)

因为\(n\)有\(\lfloor log_2n \rfloor+1\)个二进制位,因此只用\(\lfloor log_2n \rfloor\)次乘法就可以计算出\(a^1,a^2,a^4,a^8,\cdots,a^{2^{\lfloor log_2n \rfloor}}\),以3为例:

\(3^1=3\)

\(3^2=(3^1)^2=3^2=9\)

\(3^4=(3^2)^2=9^2=81\)

\(3^8=(3^4)^2=81^2=6561\)

因此为了计算\(3^{13}\),我们只需要将\(13\)对应二进制位为\(1\)的整系数幂乘起来就行了:

\(3^{13}=3^{(1101)_2}=3^8\times 3^4 \times 3^1=6561\times 81\times 3=1594323\)

将上述过程说得形式化一些,如果把\(n\)写作二进制为\(\left(n_{t} n_{t-1} \cdots n_{1} n_{0}\right)_{2}\),那么有:

\(n=n_{t} 2^{t}+n_{t-1} 2^{t-1}+n_{t-2} 2^{t-2}+\cdots+n_{1} 2^{1}+n_{0} 2^{0}\)

其中\(n_{i} \in 0,1\),那么就有:

\(a^{n}\)

\(=\left(a^{n_{t} 2^{t}+\cdots+n_{0} 2^{0}}\right)\)

\(=a^{n_{0} 2^{0}} \times a^{n_{1} 2^{1}} \times \cdots \times a^{n_{t} 2^{t}}\)

Input Format

一行两个整数\(a,n\)。

其中\(1\leq a \leq 100, 1 \leq n \leq 2\times 10^9\)

Output Format

一行一个整数\(a^n(mod~2019)\)

Sample Input 1

2 3

Sample Output 1

8

Sample Input 2

3 13

Sample Output 2

1332

ligongzzz's solution

#include <iostream>
using namespace std;

int fast_pow(int a, int n) {
    int ans = 1, base = a;
    for (; n; n >>= 1) {
        if (n & 1)
            ans = (ans * base) % 2019;
        base = (base * base) % 2019;
    }
    return ans;
}

int main() {
    int a, n;
    cin >> a >> n;
    cout << fast_pow(a, n);

    return 0;
}

q4x3's solution

#include <iostream>

using namespace std;

int main()
{
    int a, n, ans = 1;
    cin >> a >> n;
    while(n > 0) {
        if (n & 1) ans = (a * ans) % 2019;
        a = (a * a) % 2019;
        n >>= 1;
    }
    cout << ans << endl;
}