CHAPD - Editorial



Author: Vitalij Kozhukhivskij
Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng




Basic maths, greatest common divisor (gcd)


Given two numbers, determine if the first number is divisible by all prime divisors of the second number.


We are given two integers A and B, and we want to determine whether there exist a prime number which divides B, but not A.

If B = 1, then clearly there is no such prime, as B has no prime divisors.
Now assume that B > 1. Let us say d = \gcd (A, B). If any prime number divides both A and B, then it must also divide d. In other words, d contains all common prime divisors of A and B.

If d = 1, that means, there is no common prime divisor between A and B. In this case, clearly, B has a prime divisor which does not divide A, in fact all prime divisors of B fall in this category.

On the other hand, if d > 1, then B = d * (B / d). Since d contains only those primes which divide A as well, hence, B will have a prime divisor not dividing A, if and only if (B/d) has such a prime divisor. So now we have reduced the task for pair (A, B) to the pair (A, B/d). Using this we can implement an easy recursive approach as shown below.

bool HasUniquePrime(int A, int B) {
  if (B == 1) return false;

  int d = gcd(A, B);
  if (d == 1) return true;
  return HasUniquePrime(A, B/d);

Since each step reduces B by a factor greater than one, the recursion will terminate at most after (\log B) steps. Also, in each step we are calculating gcd, which takes O (\log \min (A, B)) time. Hence, the overall complexity of this approach is O (\log^2 B)

Time Complexity:

O (\log^2 B)


Author’s solution
Tester’s solution


here’s a one-liner in python:-)

print ‘Yes’ if (a**65)%b==0 else ‘No’


can you explain?

1 Like

Hello @all,

This was a really cool problem for me!! :smiley:

I spent a looong time trying the basic approach of factoring B into its distinct prime factors and trying to divide A by all of them… Obviously the challenge here was that B could be extremely large (or large for number theory lovers :stuck_out_tongue: ) and as such that task proved to be quite difficult… I was familiar with the simple sieving methods for finding prime numbers (Erathostenes, Atkin sieves) and was familiar (not implementation-wise, I can’t implement almost any algorithm without having to look it up or see my own old codes from uni) with randomized primality testing methods like Pollard-Rho thanks to previous codechef contests, so, after a very long while, my idea was to extend these methods to factorize large integers but even Pollard-Rho was proving insufficient for this… Even with small pre-calculated prime tables it was always really slow for these contraints.

Then, I found out about two very advanced algorithms (or at least, ones which were new to me) called Pollard-Brent and Elliptic Curve Method.

I managed to grasp Pollard-Brent up to a point and basically, it’s a modification made to the Pollard-Rho algorithm which makes sure that the random numbers are only computed once, which speeds up the process considerably.

Using a code I found, this algorithm manages to solve almost all sub-tasks in Python, giving TLE on 2 sub-tasks of task 2. My guess is that on those 2 tasks, the B number contains a lot of moderately large factors which might slow down my last verification of dividing A by all factors of B considerably because of a lot of mod operations. Maybe a similar code in C++ would have passed this…

Then I found the Python implementation of ECM for factorization of HUGE numbers in Python, that is inclusively available in Ubuntu Linux repos and sadly I couldn’t convert it to a decent format as the method was using generators and I couldn’t “unfold” them to lists… So I couldn’t use this although it might have passed by a slight margin only and it was obviously an overkill for this problem…

After a long while, and thinking on the totient function for some reason, I thought about the GCD and after a few hours of writing and searching online and reading, I finally managed to use the simpler GCD algorithm to get AC.

I wonder if someone got AC by fully factorizing B…




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

This is genius :smiley:

Awesome :smiley:

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

1 Like

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

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

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?

how gcd can give all prime factors…?

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

@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 ( and his program give ‘No’.

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.

Sorry, my mistake.

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

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

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

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