# 14258: 【原4258】快速幂

### 题目描述

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

## Description

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

$$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}=3^{(1101)_2}=3^8\times 3^4 \times 3^1=6561\times 81\times 3=1594323$$

$$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}$$

$$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}}$$

2 3

8

3 13

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;
}