[Binary fast powers]

For powers m to the n, say 5 to the seventh, we can rewrite 7 as binary 111, and then we can factor 5 to the seventh.

5^7^=5^(1*2 ^ 0)5^(1 *2 ^ 1)5^(1 *2 ^2);

It’s not hard to see that after the decomposition of the exponents of each term, from a macro point of view, we can see that we have changed from six multiplications to two multiplications, of course, there is no concept of multiplication in the computer, multiplication is essentially accumulation, and in this respect, the efficiency of the improvement is greater than we expected.

Now LET me talk about the implementation.

2^0-> 2^1-> 2^2(1->2->4)

We could call the first term 5 to the 1 times 2 to the 0 x, and then we could see that each successive term, we just square the previous term, and we’re incrementing. Such as

5^(1* 2 ^ 1)= 5^(1* 2 ^0) * 5^(1* 2 ^0)

5^(1 * 2 ^ 2)=5^(1 * 2 ^ 1) * 5^(1 * 2 ^ 1)

5^(1 * 2 ^ 3)=5^(1 * 2 ^ 2) * 5^(1 * 2 ^ 2)

2. Then there is the processing of coefficients, i.e. 1* 2^0, 0* 2^1…. Binary coefficient processing.

1) We can obtain the end number by n&1. If it is odd, it means that the current product term needs to be multiplied into the final result

2) Then refresh the mantissa with >> or /2.

Loop 1) 2) until n is 0;


long long Pow(long long  x,long long  n)
{
    long long  ans=x,res=1;
    while (n)
    {
         if(n&1)
         {
            res=res*ans;
         }
         ans*=ans;
         n>>=1;
    }
    return res;
}
Copy the code

【 Fast power module 】

About the modulo of large numbers we take modulo according to the total number = the product of each factor take modulo ab=((a%n)(b%n))%n; Note that exponentials can’t be modulo, and with this formula we can make simple changes to quick powers

#include <iostream>
using namespace std;
long long Pow(long long  x,long long  n,long long  a)
{
    long long  ans=x,res=1;
    while (n)
    {
         if(n&1)
         {
            res=(res*ans)%a;
         }
         ans=(ans*ans)%a;
         n>>=1;
    }
    return res;
}
Copy the code

And for that, we can do this problem minimum non-zero product of array elements