CHAPD - Editorial

editorial
, , , ,
4

To know how a code should not be, please see my solution for this problem.

1 Like
5

I simply made a sieve till 10005 and went on dividing.If still b!=1 then b must be a prime number and printed the answer accordingly.

Have a look :CHAPD Solution

6

I did something similar to hippie but to do that in C++ w/o Big Int I computed gcd and divided b by gcd a number of times and then checked gcd^70 % b==0

7

Hi ab13123002,

Can you explain why generating sieve till 10005 is working as far as i know if b = 10^18 then we should have list upto at least sqrt(10^18) = 10^9 th prime number to check all its prime divisors.but you have generated
only 1228 primes numbers and 1228th prime is “9973” i checked your code

Please explain why this approach working?

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.