You are not logged in. Please login at www.codechef.com to post your questions!

×

Need proof for One-Liner Python Solution for Problem CHAPD

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!

asked 22 May '15, 01:06

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11243
accept rate: 14%


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

link

answered 23 May '15, 21:29

dextrous's gravatar image

5★dextrous
1582210
accept rate: 0%

edited 23 May '15, 21:34

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×528
×48
×7

question asked: 22 May '15, 01:06

question was seen: 1,024 times

last updated: 23 May '15, 21:34