Need proof for One-Liner Python Solution for Problem CHAPD

general
, ,
1

Problem Link: http://www.codechef.com/problems/CHAPD/

Explanation:

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:

Solution: 
import sys
t=int(sys.stdin.readline())
for _ in range(t):
    a,b=map(int,sys.stdin.readline().split())
    if (a**65)%b==0:
        print "Yes"
    else:
        print "No"

After observing this solution I was not able to understand why did author choose value “65” whereas python cannot compute (2^64)^65 as When I tried to test extreme value i.e. 10^18, 10^18 It gave Memory Error on PC.

I tested replacing value 65 with some random values that are
64, 61, 45, 33, and 17 So I found that for value 17 one test case didn’t passed and for other values code AC’ed for all values.

You may see my submissions here.

I just want to know the logic behind this solution.

Thank You!

2

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)…