Power of number

Problem

Find the answer obtained by raising A to the power of B, modulo the prime number 10^9+7. Here, A and B are both less than or equal to 10^13.

We can find this using a simple loop. In other words, the number A is multiplied by B times, and we are talking about 10^13 times. How much action is that in general? A lot, and if you imagine that 300 million operations are performed in 1 second, then it will work for more than 9 hours. Waiting 9 hours to find a number is like a fool being patient

Analysis

B is in binary notation $$ \begin{aligned} B = \sum\nolimits_{k=0}^n b_k*2^k \end{aligned} $$

let it be decomposed. (b[k] is 0 or 1) Then n <= log(10^13). For example, 13 = 1*1 + 0*2 + 1*4 + 1*8 or 1101 in the binary number system. What do we do with the binary representation of B? If we know 2^k of A $$ A^B = \prod\nolimits_{k=0}^n A^{b_k*2^k} $$

will happen. In this way, we can find A to the power of B in n operations. Because in order to find power 2^k of any number A It is enough to know 2^(k-1) of the number A.

Recursively imagine

If the number B is even $$ A^B=(A^{B/2})^2 $$ If B is odd $$ A^B=(A^{B/2})^2 * A $$ is clear. This shows that if we want to know the A to the power of B, we can find A to the power of B/2. Then, if you want to find A to the power of B/2, all you have to do is find A to the power of B/4. In this way, when the number B is equal to the number 1, A to the power of 1 is 1 and we can know this immediately. Now we can solve this using recursion.

Additionally, the time complexity is log(B), which means that what previously would have taken several hours and approximately 10^13 operations can now be completed in less than a second with just 43 operations.

Code

#include <iostream>
using namespace std;
	
	long long mod = 1e9+7; 

long long bodolt1( long long A, long long B ) {
	long long ret = 1, now = A;

	while( B > 0 ) {
		if( B%2 == 1 ) { 
			ret = (ret*now)%mod;
		}
		now = (now*now)%mod;
		B /= 2; 
	}
	return ret;
}

long long bodolt2( long long A, long long B ) {
	if( B == 0 ) return 1LL; 
	if( B == 1 ) return A;   

	long long ret = bodolt2( A, B/2 );
	ret = (ret*ret)%mod;
	if( B%2 == 1 ) {
		ret = (ret*A)%mod;
	}
	return ret; 
}

int main() {
	long long A, B;
	cin >> A >> B;
	cout << "Solution 1-> " << bodolt1( A%mod, B ) << endl;
	cout << "Solution 2-> " << bodolt2( A%mod, B ) << endl;
	return 0;
}

Larger number, and larger power

Let’s find the remainder of A^B when divided by P (where P is a prime number). Earlier, we thought about A,B <= 10^13. Now, our limitation is that numbers A and B can have up to 10^6 digits. But P <= 10^13.

By Fermat’s Least Theorem $$ A^{P-1}\equiv 1 \mod P $$ This problem will be easy to use (try it) and here’s how $$ A^B\equiv A^{(B \mod P-1)} \mod P $$ because every A to the power of P-1 equals 1, what matters when finding A to the power of B is the remainder after dividing the number by P-1. From this, we were able to make the number B less than P.

Our number A has digits up to 10^6, so we can only read it digit by digit. Since we are only interested in the remainder after dividing A by P, we can write it as a sum to the power of 10. $$ A = \sum\nolimits_{k=0}^n (a_k*10^k \mod p) $$ This idea can also be used with the number B and thought in the same way as the previous problem.

#include <bits/stdc++.h> 	
using namespace std;
	
	long long mod;

long long solve(long long x, long long y) {
	if(y == 0) return 1;
	if(y == 1) return x%mod;
	long long ret = solve(x, y/2);
	ret = (ret*ret)%mod;
	if( y%2 ) ret = (ret*x)%mod;
	return ret;
}

int main() {
	string x, y; 
	cin >> x >> y >> mod;	

	long long a = 0, b = 0, now = 1;

	for(int i = x.size()-1; i >= 0; i--) {
		a = (a + (x[i] - '0')*now)%mod;
		now = (now*10)%mod;
	}
	
	now = 1;
	for(int i = y.size()-1; i >= 0; i--) {
		b = (b + (y[i] - '0')*now)%(mod-1);
		now = (now*10)%(mod-1);
	}
	
	cout << solve(a, b) << endl;
	return 0;
}

Even bigger numbers

Let’s think about a^b%mod. We can do a transformation and make a, b < mod. But if mod <= 10^13, the product will be approximately 10^26 at most during the calculation of a^b. But can it be done in long long type? Then you may have noticed that the previous thoughts are not correct. How to solve this? Multiplication is problematic for large numbers, so you need to get it right. Cause it will cause overflow.

Knowing x*(y/2)%mod, we can find x*y. It turns out to be the same as the idea that was used before, the problem of finding a^b. In other words, when you find the product of a number, you find it with the help of addition, and try to write the code.

Summary

Well, it’s just a power of some number, but depending on the level at which you look at it, different interesting problems arise.

Problem#

Analysis#

Recursively imagine#

Code#

Larger number, and larger power#

Even bigger numbers#

Summary#