# How to implement such algorithm?

You want to implement the algorithm for binary exponentiation
``````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?
July 4th 19 at 23:30
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;
}``````
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
S = (S * c) % mod;
should be replaced by
c*=base;
c%=mod;
c*=c;
c%=mod;
(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

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++