You want to implement the algorithm for binary exponentiation

Wrote here, and it's not working as it should. Tell me what need to fix?

```
std::vector<bool> temp = toBinary(power);
std::vector<long> result;
long S = 1, c = base;
for (auto i = 0; i < temp.size(); ++i)
{
if (temp[i] == 1)
{
S = (S * c) % mod;
std::cout << "S =" << S << std::endl;
}
else
{
c = (c * c) % mod;
std::cout << "c =" << c << std::endl;
}
}</long></bool>
```

Wrote here, and it's not working as it should. Tell me what need to fix?

asked July 4th 19 at 23:30

2 answers

answered on July 4th 19 at 23:32

```
mod_power uint64_t(uint64_t a, uint64_t b, uint64_t n) {
uint64_t bit = 0x8000000000000000ui64;
uint64_t result = a % n;
while (bit && (bit & b == 0))
bit = bit >> 1;
while ((bit = bit >> 1))
result = (result * result * ((bit & b) ? a : 1)) % n;
return result;
}
```

answered on July 4th 19 at 23:34

First, long is int32, so if you mod more than 2^15, it is better to take long long.

Second, the line

The following code works correctly:

Second, the line

S = (S * c) % mod;should be replaced by

c*=base;(if you want to follow the algorithm), in addition, to put the condition that temp[i] is not the last bit bit of number - otherwise, we are once again going to offer square

c%=mod;

c*=c;

c%=mod;

The following code works correctly:

```
long long bp(long long base, long long power)
{
std::vector<bool> temp = toBinary(power);
std::vector<long> result;
long long c = 1;
for (auto i = 0; i<temp.size(); i++) { if (temp[i]="=" 1) c="(c*base)%mod;" } if(i!="temp.size()-1)" c*="c;" c%="mod;" return c; }< code></a temp.size();></long></bool>
```

```
br><br>
I don't understand the meaning of the variable S, if you explain, perhaps, your code will be able to edit the "softer" (I think I rewrote half your code, sorry)<br><br>
Generally speaking, the function of the binary exponentiation recursively as follows:<br><pre><code lang="cpp">binpow long long(long long base, long long power)
{
if(power==0)
return 1;
if(power%2)
return (binpow(base, power-1)*base)%mod;
long long tmp = binpow(base, power/2);
return (tmp*tmp)%mod;
}</code></pre><br>
You may find it easier to write arecursive function with the recursive understanding.
```

Find more questions by tags C++