×

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

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

19.7k350498541

1

The solutions posted are for CHEFWD, not QNUMBER

(11 Sep '12, 15:42) 5★

Oops! Thanks for pointing out. This is fixed.

(11 Sep '12, 15:56)
1

Setter code gets WA

(11 Sep '12, 15:59) 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.

(11 Sep '12, 16:08) 5★

Hmmm.. This is the classic case of the tester upgrading a setter's solution to make the problem more complex and interesting :-)

The setter's solution is slower.

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

(11 Sep '12, 16:41)

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

(11 Sep '12, 18:00)
showing 5 of 6 show all

 0 Wrong solution has been uploaded. We will change it.:) answered 11 Sep '12, 17:34 11●1 accept rate: 0%
 0 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)]; answered 11 Sep '12, 23:41 5★hedgefog 15●1 accept rate: 0%
 0 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. link This answer is marked "community wiki". answered 12 Sep '12, 12:27 285●10●17●19 accept rate: 5%
 0 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. answered 26 Sep '12, 22:54 5★karan173 685●9●11●19 accept rate: 0%
 0 An Example with the editorial would make it a lot better... answered 14 Jul '16, 18:15 187●2●9 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,629
×631
×30
×18

question asked: 11 Sep '12, 15:24

question was seen: 5,416 times

last updated: 14 Jul '16, 18:15