Factors of $N^3$

Note that 71, 73, and 79 are all prime numbers, so that every divisors is of the form $d = 71^a\cdot 73^b\cdot 79^c$ with $a, b, c$ non-negative integers.

1. Count all triples $a, b, c$ with $a + b + c \leq 9$ .

Rationale: If $a + b + c > 9$ , the divisor $d$ is greater than $N$ . Proof: the smallest possible divisor with $a + b + c > 9$ is $71^{10} = (71^3\cdot 73^2\cdot 79^4) \cdot \left(\frac{71}{73}\right)^2 \cdot \left(\frac{71}{79}\right)^4 \cdot 71 > N \cdot \left(\frac12\right)^2 \cdot \left(\frac12\right)^4 \cdot 64 = N.$

Therefore the set of all triples with $a + b + c \leq 9$ is guaranteed to contain all solutions (and several more, which we subtract out later.) To do the counting, consider in how many ways a set of 9 "stars" can be partitioned by placing 3 "bars": $n_1 = \left(\begin{array}{c} 12 \\ 3\end{array}\right) = 220.$

2. Rule out all triples $a, b, c$ with $b \geq 7$ and $a + b + c \leq 9$ .

Rationale: Since $d$ must divide $N^3$ , we require $a \leq 9$ , $b \leq 6$ , and $c \leq 12$ . The conditions on $a$ and $c$ are automatically fulfilled is $a + b + c \leq 9$ , but we need to rule out the situation $b > 6$ .

To do the counting, we count "stars-and-bars" for $a + (b-7) + c \leq 2$ : $n_2 = \left(\begin{array}{c} 5 \\ 3\end{array}\right) = 10.$

3. Rule out all triples $(a, b, c) \leq (3, 2, 4)$ .

Rationale: Such triples corresponds to the divisors of $N$ itself.

The count is simply $n_3 = (3 + 1)\cdot (2 + 1)\cdot (4 + 1) = 60.$

4. Rule out the triples with $a + b + c = 9$ and $b \leq 6$ for which the divisor is too great ( $d > N)$ .

Rationale: If $a + b + c < 9$ the divisor is certainly less than $N$ . Proof: the largest possible divisor with $a + b + c < 9$ is $79^8$ , and using a similar technique as under (1) we can show it is less than $N$ . But if $a + b + c = 9$ the divisor may be either less or greater than $N$ .

(Incidentally, it is not difficult to count that there are 49 divisors for which $a + b + c = 9$ and $b \leq 6$ .)

a. We take our starting point in $N$ itself, which corresponds to $(a, b, c) = (3, 2, 4).$ (We ruled this out in step (3) above.)

b. One way to increase the divisor is to replaces factors 71 by 73 or 79; or factors 73 by 79. This corresponds to the 17 triples with $a \leq 3$ and $c \geq 4$ (but not both equal): $(3, 1, 5), (3, 0, 6), (2, 3, 4), (2, 2, 5), (2, 1, 6), (2, 0, 7), (1, 4, 4), (1, 3, 5), (1, 2, 6), \\ (1, 1, 7), (1, 0, 8), (0, 5, 4), (0, 4, 5), (0, 3, 6), (0, 2, 7), (0, 1, 8), (0, 0, 9).$

c. A more subtle way to increase the divisor is to replace two factors 73 by $71\cdot 79$ . This works because $71\cdot 79 > 73^2$ . We obtain the triple: $(a, b, c) = (4, 0, 5).$

d. Replacing a factor 79 by 73 lowers the value of the divisor; however, this can be compensated by replacing two factors 71 by 73, because $71\cdot 71\cdot 79 > 73^3$ . This gives the final triple to be ruled out: $(a, b, c) = (0, 6, 3).$

e. All other triples in this category correspond to divisors less than $N$ . They are obtained by replacing higher factors by lower factors, or by substituting $73^2$ for $71\cdot 79$ . In either case the value decreases.

Thus in this category we rule out $n_4 = 19$ cases.

Finish up:

The number of divisors that meet the conditions is $n_1 - n_2 - n_3 - n_4 = 220 - 10 - 60 - 19 = \boxed{131}.$