How to implement such algorithm?

You want to implement the algorithm for binary exponentiation
44918c4922a941e4b3d3524e79dd6d8a.PNG
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
2 answers
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++