# Problem Link:

## Setter: Misha Chorniy

## Tester: Ke Bi

## Editorialist: Rashad Mammadov

# Difficulty:

EASY

# Prerequisites:

Math, Number Theory

# Problem:

Given * N*,

*,*

**a***,*

**b***. Find the number of triples*

**c***where*

**(x, y, z)**

**N = x \cdot***,*

**y \cdot z***,*

**x \leq a***, and*

**y \leq b***.*

**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

*. We can consider all possible pairs*

**D***where (*

**(x, y)***and*

**x \in D***) and (*

**x \leq a***and*

**y \in D***). For each ***(x, y)***: if the conditions*

**y \leq b***and*

**N \equiv 0 \pmod{x \cdot y}***hold, then we have found a valid triplet.*

**z = \frac{N}{x \cdot y} \leq c*** Note:* While implementing this solution, one needs to be careful with overflows. Since

*and*

**x***can be up to*

**y***may not fit into a*

**10$^{6}***, ***x \cdot$ y***.*

**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$***. You can read more about the*

**n$^{\frac{1}{3}}*** ***\leq$ 1344***and its*

**divisor function***here.*

**growth rate*** Note:* Here

*is the size of*

**|D|**

**D**# There is another similar solution:

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

Assume we are given * n*,

*,*

**b***and we have to find the number of pairs*

**c***where*

**(y, z)***,*

**n = y \cdot z***, and*

**y \leq b***. This can be solved by considering all divisors of*

**z \leq c***. For any divisor*

**n***, we need to check whether both*

**d***and*

**d \leq b**

**\frac{n}{d}***conditions hold or not. This can be done in O(\sqrt{n}) time.*

**\leq c**Now, let’s break the original problem into simplified ones. For any divisor - * d* of

*, we can choose*

**N***if*

**x = d***, and the rest is to solve the above problem for ***n = \frac{N}{d}***.*

**d \leq a**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

*for the numbers between*

**30***and ***10$^{9}$***.*

**1**# 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)**