Problem Summary

We must count positive integer \(N\)-tuples \((x_1,\dots,x_N)\) such that

$$\gcd(x_1,\dots,x_N)\ge G,\qquad \operatorname{lcm}(x_1,\dots,x_N)\le L,$$

and return the result modulo \(101^4\). A direct search is impossible for the actual parameters, so the solution reorganizes each tuple by separating its common gcd from its normalized lcm structure.

Mathematical Approach

Let

$$F(G,L,N)=\#\left\{(x_1,\dots,x_N)\in \mathbb{Z}_{>0}^N:\gcd(x_1,\dots,x_N)\ge G,\ \operatorname{lcm}(x_1,\dots,x_N)\le L\right\}.$$

The key idea is to classify tuples by their common gcd and by the lcm that remains after dividing that gcd out.

Step 1: Normalize by the Common GCD

For any admissible tuple define

$$g=\gcd(x_1,\dots,x_N),\qquad x_i=g\,y_i.$$

Then the normalized tuple satisfies

$$\gcd(y_1,\dots,y_N)=1.$$

Now define

$$m=\operatorname{lcm}(y_1,\dots,y_N).$$

Because lcm scales linearly when every coordinate is multiplied by the same factor, we obtain

$$\operatorname{lcm}(x_1,\dots,x_N)=g\,m.$$

So once the normalized tuple is fixed, the only remaining freedom is the choice of \(g\). The constraints become

$$G\le g\le \left\lfloor\frac{L}{m}\right\rfloor.$$

Hence the number of admissible gcd values for this normalized tuple is

$$w(m)=\left\lfloor\frac{L}{m}\right\rfloor-G+1,$$

and this is positive only when

$$m\le K=\left\lfloor\frac{L}{G}\right\rfloor.$$

Step 2: Define the Normalized Counting Function

Let

$$H_N(m)=\#\left\{(y_1,\dots,y_N)\in \mathbb{Z}_{>0}^N:\gcd(y_1,\dots,y_N)=1,\ \operatorname{lcm}(y_1,\dots,y_N)=m\right\}.$$

This counts exactly the normalized tuples whose lcm is \(m\). Summing over all possible normalized lcm values gives

$$F(G,L,N)=\sum_{m=1}^{\lfloor L/G\rfloor} H_N(m)\left(\left\lfloor\frac{L}{m}\right\rfloor-G+1\right).$$

Therefore the hard part of the problem is reduced to computing \(H_N(m)\) efficiently for every \(m\le K\).

Step 3: Count One Prime Power

Write the prime factorization of \(m\) as

$$m=\prod_{p} p^{e_p}.$$

Fix one prime power \(p^e\parallel m\). For each coordinate \(y_i\), let \(\alpha_i=v_p(y_i)\). Since \(y_i\mid m\), each exponent lies in

$$\alpha_i\in\{0,1,\dots,e\}.$$

The normalized conditions translate into simple conditions on these exponents:

$$\gcd(y_1,\dots,y_N)=1 \iff \min(\alpha_1,\dots,\alpha_N)=0,$$

$$\operatorname{lcm}(y_1,\dots,y_N)=m \iff \max(\alpha_1,\dots,\alpha_N)=e.$$

So for each prime \(p^e\parallel m\), we only need to count exponent vectors in \(\{0,\dots,e\}^N\) whose minimum is \(0\) and whose maximum is \(e\).

Step 4: Inclusion-Exclusion for the Local Factor

The total number of exponent vectors is \((e+1)^N\).

Vectors with no zero exponent use only \(\{1,\dots,e\}\), so there are \(e^N\) of them.

Vectors with no exponent equal to \(e\) also number \(e^N\).

Vectors having neither \(0\) nor \(e\) use only \(\{1,\dots,e-1\}\), so there are \((e-1)^N\).

Therefore inclusion-exclusion gives the local count

$$C_e=(e+1)^N-2e^N+(e-1)^N.$$

This is the number of admissible \(p\)-adic exponent patterns for one prime power. For example, when \(e=1\), we get \(C_1=2^N-2\): all binary exponent vectors except the all-zero and all-one vectors.

Step 5: Reconstruct \(H_N(m)\)

Exponent choices for distinct primes are independent. Once an admissible exponent vector is chosen for each prime \(p^{e_p}\parallel m\), multiplying the prime-power contributions reconstructs one unique normalized tuple \((y_1,\dots,y_N)\).

Hence \(H_N(m)\) is multiplicative and factors as

$$H_N(m)=\prod_{p^{e_p}\parallel m} C_{e_p}=\prod_{p^{e_p}\parallel m}\left((e_p+1)^N-2e_p^N+(e_p-1)^N\right).$$

Step 6: Final Closed Form

Substituting the normalized count into the outer sum yields

$$\boxed{F(G,L,N)=\sum_{m=1}^{\lfloor L/G\rfloor}\left(\prod_{p^{e_p}\parallel m}\left((e_p+1)^N-2e_p^N+(e_p-1)^N\right)\right)\left(\left\lfloor\frac{L}{m}\right\rfloor-G+1\right)\pmod{101^4}.}$$

This is exactly the formula implemented by the program.

Worked Example: \((G,L,N)=(10,100,2)\)

Here

$$K=\left\lfloor\frac{100}{10}\right\rfloor=10.$$

For \(N=2\), the local factor simplifies to

$$C_e=(e+1)^2-2e^2+(e-1)^2=2.$$

So every prime dividing \(m\) contributes a factor \(2\), and therefore

$$H_2(m)=2^{\omega(m)},$$

where \(\omega(m)\) is the number of distinct prime divisors of \(m\).

Now evaluate the first few terms:

$$\begin{aligned} m=1&:&&H_2(1)=1,\quad w(1)=100-10+1=91,\quad c=91,\\ m=2&:&&H_2(2)=2,\quad w(2)=50-10+1=41,\quad c=82,\\ m=3&:&&H_2(3)=2,\quad w(3)=33-10+1=24,\quad c=48,\\ m=4&:&&H_2(4)=2,\quad w(4)=25-10+1=16,\quad c=32,\\ m=5&:&&H_2(5)=2,\quad w(5)=20-10+1=11,\quad c=22,\\ m=6&:&&H_2(6)=4,\quad w(6)=16-10+1=7,\quad c=28. \end{aligned}$$

The remaining terms are \(10,6,4,4\) for \(m=7,8,9,10\). Therefore

$$91+82+48+32+22+28+10+6+4+4=327,$$

which matches the checkpoint used by the implementation.

How the Code Works

The program first sets \(K=\lfloor L/G\rfloor\) and builds an SPF table (smallest prime factor) up to \(K\). It then precomputes

$$\texttt{local}[e]=C_e=(e+1)^N-2e^N+(e-1)^N \pmod{101^4}$$

using fast modular exponentiation. For each \(m\le K\), the SPF table gives the factorization of \(m\), so the code multiplies the relevant \(\texttt{local}[e]\) values to obtain

$$\texttt{h}[m]=H_N(m)\pmod{101^4}.$$

Finally it accumulates

$$\texttt{h}[m]\left(\left\lfloor\frac{L}{m}\right\rfloor-G+1\right)$$

for all \(1\le m\le K\), always reducing modulo \(101^4\).

Complexity Analysis

Let \(K=\lfloor L/G\rfloor\). Building the SPF sieve costs \(O(K\log\log K)\) time and \(O(K)\) memory. Factoring every \(m\le K\) via the SPF table touches each prime-power exponent once; the total divisor-stripping work has average order \(O(K\log\log K)\). Thus the overall method is near-linear in \(K\) and uses \(O(K)\) memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=350
2. Least common multiple: Wikipedia — Least common multiple
3. Greatest common divisor: Wikipedia — Greatest common divisor
4. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle
5. Multiplicative function: Wikipedia — Multiplicative function