You are not logged in. Please login at www.codechef.com to post your questions!

×

QNUMBER - Editorial

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

This question is marked "community wiki".

asked 11 Sep '12, 15:24

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 25 Dec '12, 14:53

admin's gravatar image

0★admin ♦♦
19.7k350498541

1

The solutions posted are for CHEFWD, not QNUMBER

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

Oops! Thanks for pointing out. This is fixed.

(11 Sep '12, 15:56) gamabunta1★
1

Setter code gets WA

(11 Sep '12, 15:59) bcurcio5★

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) Sumudu5★

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) gamabunta1★

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) gamabunta1★
showing 5 of 6 show all

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

link

answered 11 Sep '12, 17:34

kamranmaharov's gravatar image

6★kamranmaharov
111
accept rate: 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)];

link

answered 11 Sep '12, 23:41

hedgefog's gravatar image

5★hedgefog
151
accept rate: 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

kavishrox's gravatar image

3★kavishrox
285101719
accept rate: 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.

link

answered 26 Sep '12, 22:54

karan173's gravatar image

5★karan173
68591119
accept rate: 0%

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

link

answered 14 Jul '16, 18:15

vishveshcoder's gravatar image

4★vishveshcoder
18729
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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