 # How to use modulo (1000000007) in question where you have to use pow(x,n),basically power of number?

i am doing a problem in which i need to count total number of triangle after each move.
let me tell you a bit more about it .
" you are given a triangle and after first move it is divided into 4 equal parts (you can imagine) then those parts are further divided into four parts,the middle part in each case is not divided further.

so my solution contains an expression

long int tot=0,i,tot1=0,tot2=0;

for(i=n;i>=0;--i)
{
tot1+=(pow(3,i)) ;          //for counting all triangles which can be divided further
}

for(i=n-1;i>=0;--i)
{
tot2+=pow(3,i);          //for counting total middle part after n move
}
tot=tot1+tot2;

//I have to use modulo and i don't know how to use in expressions having power function


You have to use custom power function similar like this:

ll powmod(ll a, ll b) {
ll res = 1;
a %= mod;
assert(b >= 0);
for (; b; b >>= 1) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}


EDIT: where mod = 10^9+7, i.e. const ll mod = 1000000007;

2 Likes

@pkpawan123 Which line needs explanation??
b >>= 1 means b right shift by one, i.e. b = b/2
b & 1 checking b odd or even, i.e. b % 2 == 1
a = a * a % mod; taking mod of a where mod = 10^9+7. i.e. a = (a * a ) % mod;

Hope it’s clear now. Happy coding 1 Like

To understand how/ why this works read:

then

1 Like

this is really fruitful.Thank you

1 Like

so this will give me required modulus value of ‘a’ to power ‘b’

@pkpawan123 yes.
powmod(x,y) == x^y % mod

1 Like

got it thank you so much

1 Like

@pkpawan123 Maybe you are looking behind the algorithm, right?
If so, here is the explanation (Behind the Algorithms) from the book of Essential Algorithms
tl;dr;

Behind the Algorithms:

Sometimes a program needs to calculate a number raised to an integer power. That’s not hard if the power is small. For example, 7^3 is easy to evaluate by multiplying 7 \times 7 \times 7 = 343.
For larger powers such as 7^{102,187,291} , however, this would be fairly slow.
.
Fortunately, there’s a faster way to perform this kind of operation. This method is based on the fact that you can quickly calculate powers of a number that are themselves powers of 2.
For example, consider the value A^1 , which is simply A . From that, you can calculate A^2 because A^2 = A^1 \times A^1. Similarly, you can calculate A^4 because A^4 = A^2 \times A^2 . You can then calculate A^8 because A^8 = A^4 \times A^4 , and so on.

Now that you know how to calculate some large powers of A quickly, you need to figure out how to assemble them to produce any large power. To do that, consider the binary representation of the exponent. Each of the digits in that representation correspond to the powers of A: A^0, A^1, A^2, A^4, and so on.

For example, suppose you want to calculate A^{18}. The binary representation of 18 is 10010. Reading the binary digits from right to left, the digits correspond to the values A^0, A^1, A^2, A^4 , and A^8. You can use those special powers of A to calculate A^{18}. In this case, A^{18} = 0\times A^0+ 1\times A^1+ 0\times A^2+ 0\times A^4+1\times A^8

That’s the basis for the fast exponentiation algorithm. You build bigger and bigger powers of A and use the binary digits of the exponent to decide which of those should be multiplied into the final result.

The following pseudocode shows the algorithm:

// Perform the exponentiation.
Integer: Exponentiate(Integer: value, Integer: exponent)
Integer: result = 1
Integer: factor = value
While (exponent != 0)
If (exponent Mod 2 == 1) Then result *= factor
factor *= factor
exponent /= 2
End While

Return result
End Exponentiate


The algorithm sets result to 1. Initially, this holds value to the 0^{th} power, which is 1 for any value.

The algorithm also sets factor equal to value . This will represent the powers of value . Initially, it holds value to the first power.

The code then enters a loop that executes as long as the exponent is not zero. Inside the loop, the algorithm uses the modulus operator to see whether the exponent is odd. If it is odd, then its binary representation ends with a 1. In that case, the algorithm multiplies result by the current value of factor to include that power of value in the result.

The algorithm then multiplies factor by itself so that it represents value` raised to the next power of 2. It also divides the exponent by 2 to remove its least significant binary digits.

When the exponent reaches zero, the algorithm returns the result.

The algorithm’s loop executes once for each binary digit in the exponent. If the exponent is P, then it has log _{_2} (P) binary digits, so the algorithm runs in O(log \space P) time. That’s fast enough to calculate some pretty large values. For example, if P is 1 \space milion , log (P) is about 20, so this algorithm uses about 20 steps.

. Essential Algorithms- A practical approach to computer algorithms using Python and C# By Rod Stephens.

1 Like

If you want more detailed explanation, refer to the link Modular Exponentiation.

Peace 