CHAPD - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Easy

PREREQUISITES:

Basic maths, greatest common divisor (gcd)

PROBLEM:

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

EXPLANATION:

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 AND TESTERā€™S SOLUTIONS:

Authorā€™s solution
Testerā€™s solution

5 Likes

hereā€™s a one-liner in python:-)

print ā€˜Yesā€™ if (a**65)%b==0 else ā€˜Noā€™

26 Likes

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ā€¦

Best,

Bruno

2 Likes

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 (http://www.codechef.com/viewsolution/6930377) 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. http://www.codechef.com/viewsolution/6990595 Itā€™s not faster than trial division: http://www.codechef.com/viewsolution/6965851