How can i check if A^B is divisible by C^D

for given A,B,C and D

edit :this was asked in latest SRM div 2

How can i check if A^B is divisible by C^D

for given A,B,C and D

edit :this was asked in latest SRM div 2

Write prime factorization of A as product[(pi^ai)]. So, A^B = product[(pi^(B.ai))].

Similarly, write the expression for C^D.

Now, just take the difference of corresponding powers of primes in numerator and denominator.

If there exists a positive power of any prime in the denominator, the two expressions are not divisible.

e.g. A=8,B=3,C=4,D=2 => 2^(3x3) / 2^(2x2) => 2^(9-4) => 2^(5)/2^(0) i.e. A^B is divisible by C^D.

Thanks , got it!

pretty simple though, just couldnâ€™t do it during the live contest

Yeah, I was trying several things for this problem, but got nowhere close initially. I guess a lot of divisibility problems are solved this way. Codeforces had one yesterday too.