Rock Valley P1226 [Template] Quick Power

1. Fast power templates

prior knowledge

A number n whose binary digits must be log₂n is rounded down to the nearest whole number +1;

Quick Power Template Code

This code implements the fast power algorithm (Exponentiation by squaring) to compute ( aⁿ ) values, where ( a ) and ( n ) are integers.

int quickpow(int a, int n)
{
    int res = 1; // Initialize to 1, since any number to the 0th power is 1

    while (n) { // continue the loop when the exponent n is not 0
        if (n & 1) // if the lowest bit of n is 1 (i.e. n is odd)
            res = res * a; // multiply the current base a into the result
        a = a * a; // square the base a, which is equivalent to doubling the base and halving the exponent
        n >>= 1; // shift the exponent n one place to the right, which is equivalent to halving the exponent
    }

    return res; // return the result of the calculation
}

Now parse what each line of code does, sentence by sentence:

1. int res = 1;

   • Initializing Variablesres is 1, which is the initial value of the final result. Any number to the 0th power is 1.

2. while (n) {

   • into a loop, provided that when the indexn continues if it is not 0. The loop will continue to execute untiln Changes to 0.

3. if (n & 1)

   • Determining the current indexn Whether the number is odd or not, using bitwise arithmeticn & 1 to judge. If then (i.e., the rightmost binary bit) is 1, then it means thatn It's an odd number.

4. res = res * a;

   • in the event thatn is odd, then the current base of thea Multiply to resultres in. This step implements the multiplication operation in the fast power algorithm.

5. a = a * a;

   • Then the bottom numbera Self-riding, i.e.a change intoa^2. This step corresponds to the operation of doubling the base, which corresponds to halving the exponent.

6. n >>= 1;

   • exponentialn Shift one place to the right, i.e.n change inton / 2. This step implements the exponent halving operation in the fast power algorithm.

7. Loop back to step 2 untiln becomes 0 and exits the loop.

8. return res;

   • Returns the final calculated resultresi.e., the basea exponentialn The value of the second power.

This code utilizes the idea of fast power algorithm to optimize the computational complexity of exponentiation from ( O(n) ) to ( O(log n) ) by means of iteration and bitwise operations, which significantly improves the computational efficiency.

A figurative explanation of the fast power algorithm

Examples of fast power algorithms

[Template] Quick Power

Title Description

I'll give you three whole numbers.\(a,b,p\)seek\(a^b \bmod p\)。

input format

The input has only one line of three integers, representing\(a,b,p\)。

output format

Output a string on a linea^b mod p=swhich\(a,b,p\) are the values given in the title, respectively.\(s\) is the result of the operation.

Sample #1

Sample Input #1

2 10 9

Sample Output #1

2^10 mod 9=7

draw attention to sth.

sample explanation

\(2^{10} = 1024\)，\(1024 \bmod 9 = 7\)。

Data size and conventions

insofar as\(100\%\) The data that guarantees the\(0\le a,b < 2^{31}\)，\(a+b>0\)，\(2 \leq p \lt 2^{31}\)。

solution

This problem directly apply the template of the fast power algorithm, just need each step we add the modulo operation can be, pay attention to the data need to open long long type

#include<iostream>
using namespace std;
long long  quickpow(long long  a, long long  n,long long p)
{
	long long res = 1;
	while (n) {
		if (n & 1) res = (res * a)%p;
		a = (a * a)%p;
		n >>= 1;
	}
	return res;
}
int main()
{
	long long  a, b, p;
	cin >> a >> b >> p;
	printf("%lld^%lld mod %lld=%lld", a, b, p, quickpow(a, b, p));
	return 0;
}