Problem Link: http://www.codechef.com/problems/CHAPD/ You are given two positive integers – A and B. You have to check whether A is divisible by all the prime divisors of B. On of my friend told me this solution but I am unable to understand the logic behind this solution:
asked 22 May '15, 01:06

B < 10^18 => B < 2^60, so any prime divisor in factorization of B have power lower then 60. Then if A has all the prime divisors of B, A^60(A raised to the power 60) has to be divisible by B, and if A^60 is divisible by B, then it has all it's prime divisors and so has A. This solution is based on the fact that Python can handle large values. (A**65=A^65) The fact that your code got accepted for values except 17 is based on the tyte of values provided in the test cases. To be safe and sure of the acceptance of the code you should use 65(limiting value for 10^18 as 10^18<2^60 so in worst case if A is a power of 2 only it takes a maximum of 2 raised to power 60 and also that 2 is the smallest prime number so 60 will consider all the cases)... answered 23 May '15, 21:29
