## preface

During the summer vacation, I saw an interview question from Tencent while watching C + + face to face.

**The main idea of the problem is to find the value of (2 ^ 1e10)% 10000, which limits the time complexity.**

There are no large numbers in Java and python in C + +. I wonder if readers can answer this question.

## text

This problem can be solved by fast power.

Please listen to me in detail.

After learning about binary, we know that any number can be represented by a unique binary, that is to say**Each number can be uniquely expressed as the sum of the powers of 2 whose exponents are not repeated.**

For example, suppose B has k bits in binary representation. Then B can be expressed as:

b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+c_{k-3}2^{k-3}+……+c_{1}2^{1}+c_{0}2^{0}

### Common modes of fast exponentiation are:

**Given the values of a, B and P, find the value of (a ^ b)% p. a. B, P are all large numbers, 1 < = a, B, P < = 1e10****Given the values of a, B and P, find the value of (a * b)% p. a. B, P are all large numbers, 1 < = a, B, P < = 1e10**

### 1. (a^b)%p

From the above example:

b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+c_{k-3}2^{k-3}+……+c_{1}2^{1}+c_{0}2^{0}

Then a ^ B = a^{c~k-1~2k-1}+a^{c~k-2~2k-2}+a^{c~k-3~2k-3}+……+a^{c~1~21}+a^{c~0~20}

Because the mathematical format support is not very good, post a figure to explain it.

#### Algorithm analysis:

According to the above formula, we find that the original problem is transformed into the product of subproblems with the same form, and we can change from 2 in constant time^{k-1}Item launch 2^{k}Item.

The complexity of this algorithm is O (logn). We calculate logn 2^{K}Power, and then take logn time to select the power corresponding to binary 1 to multiply.

#### Let’s practice:Calculate the value of (a ^ b)% p

```
#include
using namespace std;
typedef long long LL;
LL a,b,p;
int main()
{
scanf("%lld%lld%lld",&a,&b,&p);
LL ans=1%p; // Initial ans
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p; // Repeated square
b>>=1;
}
printf("%lld\n",ans);
return 0;
}
```

### 2.(a*b)%p

Similar to the first template, similarly:

#### Let’s practice with a question:Find (a * b)% p

```
#include
using namespace std;
typedef long long LL;
LL a,b,p;
LL ans;
int main()
{
scanf("%lld%lld%lld",&a,&b,&p);
while(b)
{
if(b&1) ans=(ans+a)%p; // Accumulate each 2 ^ k
a=a*2%p;
b>>=1;
}
printf("%lld\n",ans);
return 0;
}
```

### matters needing attention

Because the data of fast power is very large, when using C + + to do questions, it is very slow to input test cases with simple CIN, which will lead to timeout.

Here are two suggestions:

**Add this desynchronization statement before CIN**

`cin.tie(nullptr)->sync_with_stdio(false);`

**Use scanf () to read.**

## last

There are many questions about fast power, such as fast power matrix, calculating Fibonacci number and so on.

This article only talks about the initial order of fast power. I will share higher-order fast power knowledge for you later.

Well, that’s it first. See you next time!