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
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