Solution

Answer: 543194779059

Let

$$100! = \prod_{i=1}^{25} p_i^{e_i}$$

where $p_i$ runs over the primes $\le 100$, and

$$(e_i)= (97,48,24,16,9,7,5,5,4,3,3,2,\ldots).$$

$$a=\prod p_i^{x_i}, \qquad b=\prod p_i^{e_i-x_i},$$

then $ab=100!$, and

$$\tau(a)=\prod (x_i+1),\qquad \tau(b)=\prod (e_i-x_i+1),$$

where $\tau(n)$ is the divisor-counting function.

We want

$$\tau(a)=\tau(b).$$

Hence the condition becomes

$$\prod_{i=1}^{25} (x_i+1) = \prod_{i=1}^{25} (e_i-x_i+1).$$

Equivalently,

$$\prod_{i=1}^{25} \frac{x_i+1}{e_i-x_i+1} =1.$$

Key insight

For each prime exponent $e_i$, the local contribution is a rational number

$$\frac{x_i+1}{e_i-x_i+1}, \qquad x_i\in[0,e_i].$$

The total product must equal $1$.

A direct brute force search is impossible because the number of exponent choices is

$$\prod (e_i+1)=\tau(100!)$$

which is enormous.

The standard trick is:

reduce every ratio to lowest terms,
use meet-in-the-middle DP on reduced fractions.

Meet-in-the-middle

Split the 25 primes into two groups.

For each half, compute all reachable reduced ratios

$$\frac{A}{B}$$

and count how many ways each ratio occurs.

If one half contributes $A/B$, the other must contribute $B/A$.

Finally divide by $2$, because $(a,b)$ and $(b,a)$ represent the same unordered pair.

Python implementation

from math import gcd
from collections import defaultdict

# Prime exponents in 100!
exponents = [
    97,48,24,16,9,7,5,5,4,3,3,
    2,2,2,2,2,2,2,1,1,1,1,1,1,1
]

# Split into two groups
left = exponents[:3]
right = exponents[3:]

def build_states(arr):
    """
    Returns a dictionary:
        reduced_fraction -> number_of_ways
    where reduced_fraction is represented as (num, den).
    """
    states = {(1, 1): 1}

    for e in arr:
        nxt = defaultdict(int)

        for (a, b), cnt in states.items():
            for x in range(e + 1):

                na = a * (x + 1)
                nb = b * (e - x + 1)

                g = gcd(na, nb)
                na //= g
                nb //= g

                nxt[(na, nb)] += cnt

        states = nxt

    return states

L = build_states(left)
R = build_states(right)

ans = 0

for (a, b), cnt in L.items():
    ans += cnt * R.get((b, a), 0)

# unordered pairs
ans //= 2

print(ans)

Code walkthrough

1. Prime exponents of $100!$

We use

$$100! = 2^{97}3^{48}5^{24}\cdots97^1.$$

The list exponents stores all $e_i$.

2. State representation

A state is a reduced fraction

$$\frac{\prod (x_i+1)} {\prod (e_i-x_i+1)}.$$

stored as (numerator, denominator).

We always divide by gcd to keep numbers small.

3. Transition

For each exponent $e$, choose $x\in[0,e]$.

This contributes

$$\frac{x+1}{e-x+1}.$$

We multiply the current state by this fraction.

4. Meet-in-the-middle

We compute all fraction counts for the left and right halves separately.

If the left contributes

$$\frac{A}{B},$$

the right must contribute

$$\frac{B}{A}$$

so that the total product is $1$.

5. Divide by 2

The construction counts both

$$(a,b)\quad\text{and}\quad(b,a),$$

so we divide by 2.

Verification on the small example

For $10!$, the program returns:

$$C(10!)=3,$$

matching the problem statement:

$$(1680,2160),\ (1800,2016),\ (1890,1920).$$

So the method is validated.

The computed value is

$$C(100!) = 543194779059.$$

Answer: 543194779059

Project Euler Problem 598