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

4 Likes
2

The solutions posted are for CHEFWD, not QNUMBER

1 Like
3

Oops! Thanks for pointing out. This is fixed.

4

Setter code gets WA

1 Like
5

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.

6

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.

7

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

8

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

9

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)];

10

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.

11

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.

12

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