CHAPD - Editorial

editorial
, , , ,
8

how gcd can give all prime factors…?

9

@akisingh94 , gcd will give prime factors along with other repeating common factors

10

@codermukul It does not. But the testcases are incomplete, as I already forwarded to the organizers but they didnt care ;).

For example this testcase:

999923001838986077 999945001002993931

(999983*999979*999961 and 999983^2*999979)

Should give ‘Yes’ but my (http://www.codechef.com/viewsolution/6930377) and his program give ‘No’.

11

Why in the above code snippet, the function is returning false when B=1? I think it should be true as in that case B will have no prime factors.

12

Please help me understand the time complexity O(log^2 B) of the above soln.

13

http://www.codechef.com/viewsolution/6991617

SOLUTION

14

Hi can body please tell me what wrong with my code because it’s not accepted fully. I just implemented the editorial this is link to my solution

15

In @hippie’s solution, I’ll elaborate a bit on what @mrho888 said.

Lets assume A = p1^a1 * p2^a2 … * pk^ak and B = q1^b1 * q2^b2 … qm^bm

To solve the problem, we need to see whether the set {q1…qm} is a subset of {p1…pk}. Now consider A^x: clearly if there exists any x such that A^x is not divisible by B, we can say that there is some prime in B that is not there in A and the answer to the problem is “NO”. Also, we can see that B divides A^x if and only if B contains all the prime divisors of A. Now all that remains is to find a big enough x such that B divides A^x. Now the largest necessary “x” occurs when A = p, B = p^x. Since A,B <= 10^18, with p = 2, we get the largest neccesary x as ceil(log2(10^18)) which is around 60.

PS: This was an amazing approach, kudos @hippie

1 Like
16

i claculated gcd until it came out to be one, in each step divide B by gcd and after that if B==1 print yes else no. :slight_smile:

17

http://www.codechef.com/submit/complete/618032-10171--556ad41f12d55

can someone help me with the reason of tle in above code…

18

I am getting Run time error all the time.Someone help me out.This is my solution
https://www.codechef.com/viewsolution/19190554

19

can you explain?

1 Like
20

if (p^q1)|a and (p^q2)|b,where p is a prime and q1,q2 are natural

q1/q2<65 because the “worst” case is 2^1 vs 2^64

Therefore, (p^q1)|a and (p^q2)|b <=> b|a^65

1 Like
21

This is genius :smiley:

22

Awesome :smiley:

23

Sorry, my mistake.

24

i didn’t know codechef allowed such large source files. i guess more care should be taken to prevent such submissions :stuck_out_tongue:

25

I didn’t get this can you please explain in details… please…

26

I tried to factor b, but got TLE. I used Pollard’s rho. CodeChef: Practical coding for everyone It’s not faster than trial division: CodeChef: Practical coding for everyone

27

print ‘Yes’ if (a**18)%b==0 else ‘No’
^This works too. Maybe the test cases are weak.