Given 3 numbers a b c get a^b , b^a , c^x where x is abs diff between b and a cout each one but mod 10^9+7 in ascending order. well I searched web for how to use the distributive property but didn't understand it since I am beginner,
I use very simple for loops so understanding this problem is a bit hard for me so how can I relate these mod rules with powers too in loops? If anyone can help me I would be so happy. note time limit is 1 second which makes it harder
I tried to mod the result every time in the loop then times it by the original number. for example if 2^3 then 1st loop given variables cin>>a,a would be 2, num =a would be like this a = (a % 10^9 + 7) * num this works for very small inputs but large ones it exceed time
#include <iostream>
#include <cmath>
using namespace std;
int main ()
{
long long a,b,c,one,two,thr;
long long x;
long long mod = 1e9+7;
cin>>a>>b>>c;
one = a;
two = b;
thr = c;
if (a>=b)
x = a - b;
else
x = b - a;
for(int i = 0; i < b-1;i++)
{
a = ((a % mod) * (one%mod))%mod;
}
for(int j = 0; j < a-1;j++)
{
b = ((b % mod) * (two%mod))%mod;
}
for(int k = 0; k < x-1;k++)
{
c = ((c % mod) * (thr%mod))%mod;
}
}
I use very simple for loops [...] this works for very small inputs, but large ones it exceeds time.
There is an algorithm called "exponentiation by squaring" that has a logarithmic time complexity, rather then a linear one.
It works breaking down the power exponent while increasing the base.
Consider, e.g. x355. Instead of multiplying x 354 times, we can observe that
x355 = x·x354 = x·(x2)177 = x·x2·(x2)176 = x·x2·(x4)88 = x·x2·(x8)44 = x·x2·(x16)22 = x·x2·(x32)11 = x·x2·x32·(x32)10 = x·x2·x32·(x64)5 = x·x2·x32·x64·(x64)4 = x·x2·x32·x64·(x128)2 = x1·x2·x32·x64·x256
That took "only" 12 steps.
To implement it, we only need to be able to perform modular multiplications safely, without overflowing. Given the value of the modulus, a type like std::int64_t
is wide enough.
#include <iostream>
#include <cstdint>
#include <limits>
#include <cassert>
namespace modular
{
auto exponentiation(std::int64_t base, std::int64_t exponent) -> std::int64_t;
}
int main()
{
std::int64_t a, b, c;
std::cin >> a >> b >> c;
auto const x{ b < a ? a - b : b - a };
std::cout << modular::exponentiation(a, b) << '\n'
<< modular::exponentiation(b, a) << '\n'
<< modular::exponentiation(c, x) << '\n';
return 0;
}
namespace modular
{
constexpr std::int64_t M{ 1'000'000'007 };
// We need the mathematical modulo
auto from(std::int64_t x)
{
static_assert(M > 0);
x %= M;
return x < 0 ? x + M : x;
}
// It assumes that both a and b are already mod M
auto multiplication_(std::int64_t a, std::int64_t b)
{
assert( 0 <= a and a < M and 0 <= b and b < M );
assert( b == 0 or a <= std::numeric_limits<int64_t>::max() / b );
return (a * b) % M;
}
// Implements exponentiation by squaring
auto exponentiation(std::int64_t base, std::int64_t exponent) -> std::int64_t
{
assert( exponent >= 0 );
auto b{ from(base) };
std::int64_t x{ 1 };
while ( exponent > 1 )
{
if ( exponent % 2 != 0 )
{
x = multiplication_(x, b);
--exponent;
}
b = multiplication_(b, b);
exponent /= 2;
}
return multiplication_(b, x);
}
}