QNUMBER - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY

EASY-MEDIUM

PREREQUISITES

Elementary Number Theory, Integer Factorization

PROBLEM

You are given a number N. Answer for 3 types of queries

  • Given K, find the numbers that are divisors to both N and K
  • Given K, find the numbers that are divisors to N and divisible by K
  • Given K, find the numbers that are divisors of N and not divisible by K

QUICK EXPLANATION

We can factorize N into primes and store it with us.

Now for each query, we simply iterate through prime factors of N and find the power of the prime factor that occurs in K to answer each type of query. We know that there are O(log N) factors of either N or K. Thus, our algorithm will run in O(Q*(log N + log K)) time, which is sufficiently fast within the time limits.

EXPLANATION

We can factorize N by trial division in O(√N) time.

Let the factorization of N be P1R1P2R2…PmRm, for m prime factors. m can be at most O(log N).

For each of the queries, given K, we need to find the largest power of each prime in the set P = { P1, P2 …, Pm}, that occurs in K. This can be done by trial division of K by each of the primes. K will be divided at most O(log K) times.

We will obtain a set S = { S1, S2 …, Sm}, the highest power of each prime in the set P.
This will execute in at most O(log N) + O(log K) time.

Type 1 query

The result is the number of divisors of the number whose prime factorization over the set P is
T = { min(S1, R1), min(S2, R2) …, min(Sm, Rm)}.

This is equal to
∏i=1 to m(Ti + 1).

Type 2 query

If, for any i = 1 to m: Si > Ri, the answer is 0.

Otherwise the answer can be calculated by finding the number of divisors of the number whose prime factorization over the set P is
T = { R1 - S1, R2 - S2 …, Rm - Sm}.

This is equal to
∏i=1 to m(Ti + 1).

Type 3 query

The answer for this query is equal to the number of divisors of N - (the answer for the equivalent Type 2 query).

Thus if the query is not of type 1, we always find the answer to type 2 query and find the appropriate answer based on whether the query was of Type 2 or Type 3.

See the setters / testers solutions for implementation details.

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

5 Likes
2

Wrong solution has been uploaded. We will change it.:slight_smile:

3

Alternatively, we could preprocess for each divisor of N, a[] = how many other divisors of N divide it and b[] how many other divisors of N are divisible by it. Queries 2 and 3 then have constant time if we use a hash too look for K among the divisors of N. Query 1 has log(N) complexity, as the answer is a[gcd(n, k)];

4

the question was too harsh on c/c++ users . even after applying a better sieve operation code gave tle while it was AC in java for a poorer sieve . I think a minor glitch in the code should not be given tle if the logic is correct . the time limit was too harsh really.

5

how can it be said that the no. of distint prime factors is O(logn). Also please format the article properly since some maths symbols are not rendering correctly.

1 Like
6

An Example with the editorial would make it a lot better…

7

The solutions posted are for CHEFWD, not QNUMBER

1 Like
8

Oops! Thanks for pointing out. This is fixed.

9

Setter code gets WA

1 Like
10

Indeed, that setter code is using 32-bit ints (N and K should be 64-bit), plus it takes O(max(N, K)) per query which is certainly too slow.

11

Hmmm… This is the classic case of the tester upgrading a setter’s solution to make the problem more complex and interesting :slight_smile:

The setter’s solution is slower.

Please consider the tester’s solution as the model solution for this problem.

12

Hey guys! Setters solution has been re-uploaded. If you see the same old solution, make sure you have cleared your cache.

13

How ?

14

Note: we can represent any number as prime factors for eg.
Z= p1^a * p2^b * p3^c * … pk ^t
here by keyword TOTAL FACTORS I mean a + b + c + … + t

Now,
lets assume that number X is only built of the smallest prime factor which is 2
then we can write X as follows :
X = 2 * 2 * 2 … 2 [2 multiplied k times]
then, X = 2^k
by taking log base 2 on both sides gives you :
log base2 (X) = k ;

k tells us the number of times 2 is multiplied to give us X, and k = log base2 (X)

now what happens if, we unknowingly change one of the k factors by 3,
we get new number :
X1 = 3 * 2 * 2 * 2 * … * 2 [ number of 2s reduces to k -1 as a factor 2 got replaced by 3]

Also, to get a number X2 smaller than or equal to X there are two ways :
a. only reduce the number of 2s, i.e. frequency of prime factor 2 to be less than k
X2 = 2^(k-1) < X or X2 = 2^k = X

                                    **OR**

b. replace few 2s by other primes like 3,5,7, etc., by ensuring the product doesn’t exceeds k.
X2 = 2^(k -4) * 3 * 5 < X [The more 2s gets replaced by other primes the lesser the number of TOTAL FACTORS (in this problem it’s m) will be to ensure X2 <= X ]

clearly you can see X1 > X >= X2
Since, we assumed X =2 ^ k , which has log base2 (K) factors, also we showed for X2 to be less than or equal to X, number X2 has to have TOTAL FACTORS less than or equal to K.
Here, in this problem m is equivalent to TOTAL FACTORS of N
thus m <= O(log N).

Hope this helps.