QNUMBER - Editorial

editorial
factors
number-theory
sep12

#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


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


#6

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


#7

The solutions posted are for CHEFWD, not QNUMBER


#8

Oops! Thanks for pointing out. This is fixed.


#9

Setter code gets WA


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