PROBLEM LINK:DIFFICULTYEASYMEDIUM PREREQUISITESElementary Number Theory, Integer Factorization PROBLEMYou are given a number N. Answer for 3 types of queries
QUICK EXPLANATIONWe 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. EXPLANATIONWe can factorize N by trial division in O(√N) time. Let the factorization of N be P_{1}^{R1}P_{2}^{R2}...P_{m}^{Rm}, 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 = { P_{1}, P_{2} ..., P_{m}}, 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 = { S_{1}, S_{2} ..., S_{m}}, the highest power of each prime in the set P. Type 1 queryThe result is the number of divisors of the number whose prime factorization over the set P is This is equal to Type 2 queryIf, for any i = 1 to m: S_{i} > R_{i}, 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 = { R_{1}  S_{1}, R_{2}  S_{2} ..., R_{m}  S_{m}}. This is equal to Type 3 queryThe 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 SOLUTIONCan be found here TESTERS SOLUTIONCan be found here
This question is marked "community wiki".
asked 11 Sep '12, 15:24
showing 5 of 6
show all

Wrong solution has been uploaded. We will change it.:) answered 11 Sep '12, 17:34

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

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

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

An Example with the editorial would make it a lot better... answered 14 Jul '16, 18:15

The solutions posted are for CHEFWD, not QNUMBER
Oops! Thanks for pointing out. This is fixed.
Setter code gets WA
Indeed, that setter code is using 32bit ints (N and K should be 64bit), plus it takes O(max(N, K)) per query which is certainly too slow.
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.
Hey guys! Setters solution has been reuploaded. If you see the same old solution, make sure you have cleared your cache.