Czas rzędu O(log(n))
#include <iostream>
using namespace std;
using ull = unsigned long long;
const int MODULO {519};
ull power2modulo( ull number )
{
ull result {1};
ull power {2};
while( number > 0 )
{
if( number&1 ) result = result*power % MODULO;
power = power*power % MODULO;
number >>= 1;
}
return result;
}
int main()
{
cout << power2modulo(1000000000) << endl;
}