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.