INTREP - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY

PROBLEM:

Given a positive integer N, find positive integers A and B such that A-B=N and the number of distinct prime factors of A and of B are equal.

EXPLANATION:

Notation: Let d(x) represent the number of distinct prime factors of x.

The trivial case of N\equiv0\pmod 2 is solved by A=2*N and B=N.

How?

Since N is even, it’s prime factorization includes the number 2. Thus, 2*N has the same number of distinct prime factors as N.

Therefore, d(A)=d(B), and A-B=N.

The solution for when N is not divisible by 2 is not so straightforward. But a little bit of experimenting (and extrapolating the trivial case above) gives the following idea.

Claim: There exists values k_1,k_2 such that A=Nk_1 and B=Nk_2 is a valid answer.

Intuition for the next step

This may sound absurd, but let’s assume the above claim is true and try to find some special properties of k_1 and k_2.

N = A-B = N(k_1-k_2) implies k_1=k_2+1.

Our Spidey intuitive sense guides us to experiment with k_1 as a prime number. Trial and error for several small N shows that the smallest odd prime k_1 not a factor of N always works.

This little conclusion gives rise to the ingenious solution presented below.

Let x be the smallest odd prime that doesn’t divide N. Then k_1=x and k_2=x-1 are valid values for A=Nk_1 and B=Nk_2 respectively.

Proof

A-B=Nk_1-Nk_2=N(k_1-k_2)=N completes the first part of the proof.

All we need to show now is d(Nk_1)=d(Nk_2).

Since k_1 is an odd prime that is not a factor of N, we have d(Nk_1)=1+d(N).
Now, k_2=k_1-1 is even (has 2 as a prime factor), and its prime factors are <x. Since by the definition of x, all odd primes <x are factors of N, it follows that the only prime factor of k_2 not a factor of N, is 2.

Thus, d(Nk_2)=1+d(N)=d(Nk_1) and we are done.

All that remains is to find the smallest odd prime x that doesn’t divide N. This can be done by hard coding an array of the first 20 primes (why are 20 sufficient?) and iterating over it to find the required value.

Then, A=Nx and B=N(x-1) is a valid solution.

TIME COMPLEXITY:

Iterating over the constant size list of primes to determine the answer makes the time complexity

O(1)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here.

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2

can any one please provide test case where my code is node running https://www.codechef.com/viewsolution/51599135

3

What is wrong when you iterate over all odd numbers from 3 and find the smallest odd number which doesn’t divide n ? basically it will give the same answer as check all odd primes, why is it giving wrong answer ??

4

Consider n = 105 = 3 * 5 * 7, then smallest odd number which doesn’t divide n is 9. But 105 * 9 = 3^3 * 5 * 7 have 3 distinct prime factors, while 105 * 8 = 2^3 * 3 * 5 * 7 have 4 distinct prime factors.

1 Like
5

nice problem .thank you so much

1 Like
6

constraints were so intuitive to right brute force from 1 to 100 for each multiple of N.
As n<=1e16 and Max_a<=1e18.

1 Like
7

The number that you have to use is the smallest odd prime, not smallest odd number. In this case you would use 13.

8

@kabra_neel this is the answer to @bharat_1612 . Right @vasyl_protsiv ??

9

@soulmortal07
1
15

10

Feel really stupid on hindsight.

11

could you please explain me in case when n is odd, then why we are taking np and n(p-1) not np and n(p+1)

12

we know that x-1 will be an even no. but what is the gurantee that x/2 is a factor of n

13

Even that would work perfectly!
Note: Just make sure that the bigger number is printed first.

14

I think your question is why (x-1)/2 is a factor of N (not x/2) .
Now (x-1)/2 is either prime or multiple of prime numbers which are less than x . As x is the smallest odd prime number that doesn’t divide N , N is divisible by all prime numbers less than x . So N is divisible by (x-1)/2 , i.e. (x-1)/2 is a factor of N .

1 Like