Given very very large numbers a, b, c, d.Find whether a^b is divisible by c^d. (pow in c++)
Constraints: 1 <= a, b, c , d <= 10^16
Let x = (a^b) / (c^d) where x is some integer obtained after division.Applying log on both sides,
log(x) = log( (a^b) / (c^d) )
= log(a^b) - log(c^d)
= b log a - d log c
Now, x = exp(b log a - d log c) [where exp (in c++)Returns the base-e exponential function of x, which is e raised to the power x:
ex
.]Finally check, whether x is an integer or not.
C++ Implementation:
/*
Author: Prasad SVD
Definitions:
a^b -> a raised to the power of b
a^b -> pow(a, b) in C++ defined in cmath library
*/
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
long long int a, b, c, d;
double quotient;
int T;
cin >> T;
while(T > 0)
{
cin >> a >> b >> c >> d;
if(!d)
{
cout<<"a^b is Divisible by c^d"<<endl;
}
else
{
quotient = exp((b*log(a))-(d*log(c)));
cout<<quotient<<endl;
if(quotient - (int)quotient != 0)
cout<<"a^b is Not Divisible by c^d"<<endl;
else
cout<<"a^b is Divisible by c^d"<<endl;
}
--T;
}
return 0;
}
No comments:
Post a Comment