Saturday, August 23, 2014

Divisibility check for very very large numbers. Find whether a ^ b is divisible by c ^ d. (a ^ b : a raised to the power of b)

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;
}