Detailed mathematical approach

Problem Summary

Problem 747 asks for a cumulative counting function \(\Psi(n)\) attached to the triangular-pizza configurations, and the required output is \(\Psi(10^8)\bmod (10^9+7)\). The C++, Python, and Java implementations do not enumerate configurations directly. Instead, they use an exact decomposition into a closed-form cubic base term and a correction term indexed by integer pairs \((x,y)\).

Mathematical Approach

The implementations evaluate an exact prefix formula

$\Psi(n)=B(n)+C(n),\qquad B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$

The polynomial \(B(n)\) is the easy family already simplified algebraically. The interesting part is the correction term \(C(n)\), which recovers the remaining configurations by a structured scan over integer parameters.

Step 1: Start from the closed-form base term

For every \(n\), the implementations begin with

$B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$

This is a cubic polynomial, so it can be evaluated in constant time. The rest of the work is to add the nontrivial part that depends on three positive integers constrained by a quadratic boundary.

Step 2: Parameterize the remaining configurations by \((x,y,z)\)

The correction term is organized by choosing

$1\le x\le y,\qquad 4xy\le n.$

For each such pair, the third integer \(z\) can never exceed

$z_{\max}=n-1-x-y.$

So only values \(z\le z_{\max}\) are relevant. The restriction \(x\le y\) removes one symmetry in advance; a separate multiplicity factor restores that symmetry later.

Step 3: Derive the lower bound for \(z\)

The boundary test used by the implementations is equivalent to

$z^2\ge 4(x+y+z+1)xy.$

Move the mixed term to the left and complete the square:

$z^2-4xyz\ge 4xy(x+y+1),$

$\left(z-2xy\right)^2\ge 4xy(x+1)(y+1).$

Therefore the smallest admissible integer \(z\) is

$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil.$

If \(z_{\min}>z_{\max}\), then the pair \((x,y)\) contributes nothing.

Step 4: Count the admissible \(z\)-values exactly

If the interval \([z_{\min},z_{\max}]\) is nonempty, a first count gives

$2\left(z_{\max}-z_{\min}+1\right),$

because each admissible \(z\) normally corresponds to two symmetric configurations. There is one exceptional boundary case: when

$z_{\min}^2=4(x+y+z_{\min}+1)xy,$

the lower endpoint lies exactly on the symmetry boundary, so the doubled count overcounts by \(1\). Define

$\varepsilon(x,y)=\begin{cases} 1,&z_{\min}^2=4(x+y+z_{\min}+1)xy,\\ 0,&\text{otherwise.} \end{cases}$

Then the exact local count is

$c(x,y)=2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y).$

Step 5: Restore the remaining symmetries

Two outer multiplicities remain. First, when \(x\ne y\), swapping \(x\) and \(y\) creates a distinct configuration, while the diagonal case \(x=y\) should be counted only once. So define

$\mu(x,y)=\begin{cases} 1,&x=y,\\ 2,&x\ne y. \end{cases}$

Second, the formula applies an additional factor \(3\), reflecting the three equivalent placements treated symmetrically in the triangular setting. Hence

$C(n)=3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\,c(x,y).$

Step 6: Final exact formula

Combining the cubic base term with the corrected pair sum gives

$\Psi(n)=\frac{(n+18)(n-1)(n-2)}{6}+3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\left(2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y)\right),$

where

$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil,\qquad z_{\max}=n-1-x-y.$

This is exactly the quantity computed by the implementations before the final reduction modulo \(10^9+7\).

Worked Example: \(n=10\)

The base term is

$B(10)=\frac{(10+18)(10-1)(10-2)}{6}=336.$

The pair scan only needs pairs with \(4xy\le 10\). The pair \((x,y)=(1,1)\) gives

$z_{\min}=2+\left\lceil\sqrt{16}\right\rceil=6,\qquad z_{\max}=10-1-1-1=7.$

So the preliminary doubled count is

$2(7-6+1)=4.$

Because

$6^2=4(1+1+6+1)\cdot 1\cdot 1=36,$

the boundary correction subtracts \(1\), leaving \(c(1,1)=3\). Since \(x=y\), the symmetry factor is \(\mu(1,1)=1\), so the contribution is

$3\cdot 1\cdot 3=9.$

The next candidate pair \((1,2)\) already fails because

$z_{\min}=4+\left\lceil\sqrt{48}\right\rceil=11>z_{\max}=6.$

Therefore

$\Psi(10)=336+9=345,$

which matches the exact checkpoint used by the implementation.

How the Code Works

The C++ implementation evaluates the prefix sum exactly in 128-bit integer arithmetic, using corrected integer square roots so that the floor and ceiling values are mathematically exact. It loops over \(x\) while \(4x^2\le n\), then over \(y\ge x\) while \(4xy\le n\), computes the admissible \(z\)-interval, applies the one-point boundary correction when equality occurs, and accumulates the weighted contribution.

The Java implementation uses the same pair enumeration and the same exact integer-square-root logic, but it carries the arithmetic modulo \(10^9+7\) throughout so that the cubic base term never overflows. The Python implementation is a thin wrapper around the same C++ algorithm: it compiles the C++ program when necessary, executes it, and returns the parsed answer.

Complexity Analysis

The outer loop satisfies \(x\le \sqrt{n/4}\). For a fixed \(x\), the inner loop runs for

$y=x,x+1,\dots,\left\lfloor\frac{n}{4x}\right\rfloor.$

Hence the number of visited pairs is

$\sum_{x\le \sqrt{n/4}}\left(\left\lfloor\frac{n}{4x}\right\rfloor-x+1\right)=O(n\log n).$

Each pair is processed in constant time, so the total running time is \(O(n\log n)\) with \(O(1)\) auxiliary memory. In practice the hyperbolic constraint \(4xy\le n\) makes the scan far smaller than a full quadratic search.

Footnotes and References

1. Problem page: Project Euler 747
2. Integer square root: Wikipedia - Integer square root
3. Floor and ceiling functions: Wikipedia - Floor and ceiling functions
4. Completing the square: Wikipedia - Completing the square
5. Symmetry in mathematics: Wikipedia - Symmetry (mathematics)