CTHREE - Editorial

general
, , , ,
1

Problem Link:

Practice

Contest

Setter: Misha Chorniy

Tester: Ke Bi

Editorialist: Rashad Mammadov

Difficulty:

EASY

Prerequisites:

Math, Number Theory

Problem:

Given N, a, b, c. Find the number of triples (x, y, z) where N = x \cdot y \cdot z, x \leq a, y \leq b, and z \leq c.

Explanation:

This is a nice and easy math problem. Let’s find all divisors of the number N and store them in a container. Let’s call it D. We can consider all possible pairs (x, y) where (x \in D and x \leq a) and (y \in D and y \leq b). For each (x, y): if the conditions N \equiv 0 \pmod{x \cdot y} and z = \frac{N}{x \cdot y} \leq c hold, then we have found a valid triplet.

Note: While implementing this solution, one needs to be careful with overflows. Since x and y can be up to 10$^{6}***, ***x \cdot$ y may not fit into a 32-bit integer.

The time complexity of this solution is O(|D|^{2}) or can be estimated roughly as O(N$^{\frac{2}{3}})***. For the numbers between ***1*** and ***10^{9}***, ***|D|*** ***\approx$ n$^{\frac{1}{3}}*** ***\leq$ 1344. You can read more about the divisor function and its growth rate here.

Note: Here |D| is the size of D

There is another similar solution:

First, let’s solve a simplified version of the given problem.

Assume we are given n, b, c and we have to find the number of pairs (y, z) where n = y \cdot z, y \leq b, and z \leq c. This can be solved by considering all divisors of n. For any divisor d, we need to check whether both d \leq b and \frac{n}{d} \leq c conditions hold or not. This can be done in O(\sqrt{n}) time.

Now, let’s break the original problem into simplified ones. For any divisor - d of N, we can choose x = d if d \leq a, and the rest is to solve the above problem for n = \frac{N}{d}.

The overall complexity of this solution becomes O(\displaystyle\sum_{d|N} \sqrt{\frac{N}{d}}). This can also be written as O(\sqrt{N} \cdot \displaystyle\sum_{d|N} \sqrt{\frac{1}{d}}).

\displaystyle\sum_{d|N} \sqrt{\frac{1}{d}} - part is fairly small, as it is under 30 for the numbers between 1 and 10$^{9}$.

Time Complexity:

O(|D|^{2}) or O(N$^{\frac{2}{3}})*** or ***O(\sqrt{N} \cdot \displaystyle\sum_{d|N} \sqrt{\frac{1}{d}}$), per test case.

Space Complexity:

O(|D|) or O(1)

1 Like
2

My solution(overkill):

Express N in terms of prime factors

Lets say N=2^p * 3^q * 5^r * 7^s

So we have to find (p1,q1,r1,s1),(p2,q2,r2,s2),(p3,q3,r3,s3) such that (p1+p2+p3,q1+q2+q3,r1+r2+r3,s1+s2+s3)=(p,q,r,s) and 2^p1 * 3^q1 * 5^r1 * 7^s1<=a,…

My solution: https://www.codechef.com/viewsolution/17475951

1 Like
3

@mamedov can you explain why this works? “conditions N≡0(modx⋅y) and z = N/x⋅y”

4

We have chosen x and y valid before, so if it is possible to find a valid z, too that means we have found a valid triple (x, y, z). Simply, these two conditions are for checking is there a valid z for this (x, y) pair.