Detailed mathematical approach

Problem Summary

For each positive integer \(n\), consider every subset \(S\) of the divisors of \(n\). Give that subset the weight

$w(S)=\prod_{d\in S}\Phi_d(2),$

where \(\Phi_d(x)\) is the \(d\)-th cyclotomic polynomial. Let \(P(n)\) be the total weight of those subsets whose least common multiple is exactly \(n\). The cumulative target is

$Q(N)=\sum_{n=1}^{N} P(n),$

computed modulo \(10^9+7\) for \(N=10^7\). A brute-force search would enumerate all divisor subsets for every \(n\), so the fast solution rewrites the problem as a pair of divisor transforms followed by Möbius inversion.

Mathematical Approach

Write \(\mu\) for the Möbius function and \(M(x)=\sum_{k\le x}\mu(k)\) for the Mertens function. The implementations are based on the following chain of identities.

Step 1: Express the cyclotomic value at \(x=2\)

The classical factorization

$x^n-1=\prod_{d\mid n}\Phi_d(x)$

can be inverted on the divisor lattice, which gives

$\Phi_n(x)=\prod_{d\mid n}\left(x^d-1\right)^{\mu(n/d)}.$

Evaluating at \(x=2\), define

$C(n)=\Phi_n(2)=\prod_{d\mid n}\left(2^d-1\right)^{\mu(n/d)}=\prod_{k\mid n}\left(2^{n/k}-1\right)^{\mu(k)}.$

The second form matches the efficient loop structure directly: when \(\mu(k)=1\) we multiply by \(2^m-1\), when \(\mu(k)=-1\) we multiply by its modular inverse, and when \(\mu(k)=0\) nothing happens.

Step 2: Encode all divisor subsets in one product

For a fixed \(n\), each divisor \(d\mid n\) is either excluded from a subset or included with weight \(C(d)\). Therefore

$A(n)=\prod_{d\mid n}\left(1+C(d)\right)$

is exactly the generating product for all subsets of divisors of \(n\). Expanding it gives

$A(n)=\sum_{S\subseteq D(n)} \prod_{d\in S} C(d),$

where \(D(n)\) denotes the divisor set of \(n\). With the convention used by the direct check, \(\operatorname{lcm}(\emptyset)=1\) and the empty subset has weight \(1\).

Step 3: Group the expanded terms by their least common multiple

Every divisor selected in a subset \(S\) divides \(n\), so \(\operatorname{lcm}(S)\) is itself a divisor of \(n\). Define \(P(m)\) as the total weight of those subsets whose least common multiple is exactly \(m\). Then every term in the expansion of \(A(n)\) belongs to exactly one divisor \(m\mid n\), and therefore

$A(n)=\sum_{m\mid n} P(m).$

This is the crucial compression step: instead of remembering the subset itself, we only remember the final lcm that the subset generates.

Step 4: Recover the primitive contribution with Möbius inversion

The previous identity is a divisor sum, so Möbius inversion gives

$P(n)=\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$

That formula removes all contributions that already belong to proper divisors of \(n\). It replaces exponential subset enumeration with a purely arithmetic transform.

Step 5: Sum all primitive terms at once

The required total is

$Q(N)=\sum_{n\le N}P(n)=\sum_{n\le N}\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$

Write \(n=md\). Then

$Q(N)=\sum_{m\le N} A(m)\sum_{d\le N/m}\mu(d)=\sum_{m\le N} A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$

This is the final form used by the implementations. Once all values \(A(m)\) and the prefix values of \(M\) are known, the answer is obtained in one linear sweep.

Worked Example: \(n=6\) and \(N=6\)

Using the cyclotomic product,

$C(6)=\frac{(2^6-1)(2^1-1)}{(2^2-1)(2^3-1)}=\frac{63\cdot1}{3\cdot7}=3.$

Together with \(C(1)=1\), \(C(2)=3\), and \(C(3)=7\), this gives

$A(6)=\left(1+C(1)\right)\left(1+C(2)\right)\left(1+C(3)\right)\left(1+C(6)\right)=2\cdot4\cdot8\cdot4=256.$

We also have \(A(1)=2\), \(A(2)=8\), and \(A(3)=16\). Möbius inversion yields

$P(6)=A(6)-A(3)-A(2)+A(1)=256-16-8+2=234.$

For the cumulative quantity we use \(A(4)=48\), \(A(5)=64\), and the Mertens values \(M(6)=-1\), \(M(3)=-1\), \(M(2)=0\), \(M(1)=1\). Therefore

$Q(6)=2(-1)+8(-1)+16(0)+48(1)+64(1)+256(1)=358,$

which agrees with direct subset enumeration on small input.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. First they compute the Möbius function up to \(N\) with a linear sieve and convert it into prefix Mertens values modulo \(10^9+7\).

Next they precompute the sequence \(2^m-1 \pmod{10^9+7}\) together with modular inverses. A divisor-style loop then constructs every \(C(n)=\Phi_n(2)\) simultaneously by applying the Möbius product to all multiples of each index.

After that, a second divisor loop multiplies \(1+C(d)\) into every multiple of \(d\). This builds the generating product \(A(n)\) for all \(n\le N\) at once.

The final pass accumulates

$A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$

for all \(m\) from \(1\) to \(N\). A small exact check on tiny inputs confirms that this transformed formula matches explicit subset enumeration.

Complexity Analysis

The linear sieve is \(O(N)\). Constructing all cyclotomic values \(C(n)\) uses a harmonic divisor loop of size \(\sum_{k\le N}\lfloor N/k\rfloor = O(N\log N)\), and building all products \(A(n)\) has the same order. The final Mertens-weighted accumulation is \(O(N)\). Hence the overall running time is \(O(N\log N)\), while the arrays for Möbius values, prefix sums, cyclotomic values, and divisor products require \(O(N)\) memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=797
2. Cyclotomic polynomial: Wikipedia — Cyclotomic polynomial
3. Möbius function: Wikipedia — Möbius function
4. Möbius inversion formula: Wikipedia — Möbius inversion formula
5. Mertens function: Wikipedia — Mertens function