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: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.