Project Euler 747
Project Euler 747
题目
Triangular Pizza
Mamma Triangolo baked a triangular pizza. She wants to cut the pizza into \(n\) pieces. She first chooses a point \(P\) in the interior (not boundary) of the triangle pizza, and then performs \(n\) cuts, which all start from \(P\) and extend straight to the boundary of the pizza so that the \(n\) pieces are all triangles and all have the same area.
Let \(\psi(n)\) be the number of different ways for Mamma Triangolo to cut the pizza, subject to the constraints.
For example, \(\psi(3)=7\).
Also \(\psi(6)=34\), and \(\psi(10)=90\).
Let \(\Psi(m)=\displaystyle\sum_{n=3}^m \psi(n)\). You are given \(\Psi(10)=345\) and \(\Psi(1000)=172166601\).
Find \(\Psi(10^8)\). Give your answer modulo \(1\,000\,000\,007\).
解决方案
把大三角形（设顶点分别表示\(A,B,C\)）的总面积归一化为 \(1\)，则每个小三角形的面积都为 \(1/n\)。由于所有切线都从点 \(P\) 出发，所以每个小三角形都以 \(P\) 为一个顶点，其底边落在大三角形的某一条边上。
如果某个顶点（设为 \(A\)）没有被任何一条从 \(P\) 出发的切线直接连到，那么包含该顶点的那一块小三角形，其两条边界切线必须共线（也就是说，它们实际上是同一条经过 \(P\) 的直线，分别延伸到与 \(A\) 相邻的两条边上）。
如果有两个顶点都不被直接连到，就会同时出现两组这样的共线切线结构；这会使整体剖分发生冲突，无法保持所有分块都是三角形。
因此，合法情形只有两类：三条顶点都被切到，恰好一个顶点不被直接切到。
接下来计算第一类解的数量。
如果 \(PA,PB,PC\) 都是切线，那么大三角形被分成三个以 \(P\) 为公共顶点的子三角形。设这三个子三角形分别包含的小三角形个数为 \(u,v,w\)，则：\(u,v,w \ge 1,u+v+w=n.\)
对于一个固定的子三角形（顶点在 \(P\)），若要把它切成若干个等面积小三角形，方式是唯一的：把对应底边按等长（等面积）分点，再连到 \(P\)。因此一旦 \((u,v,w)\) 确定，切法唯一。
所以这一类的数量就是正整数拆分数：\(\psi_1(n)=\#\{u+v+w=n,u,v,w\ge 1\}=\dbinom{n-1}{2}.\)
接下来计算第二类解的数量。
不妨设顶点 \(A\) 不被直接切到（最后乘 \(3\)）。设切出 \(A\) 的那块小三角形为 \(ADE\)，其中 \(D\in AB, E\in AC\)，且线段 \(DE\) 经过 \(P\)。这块小三角形面积必须是 \(1/n\)。
我们定义：\(\lambda = AD/AB,\mu = AE/AC,\xi = DP/DE\)，因此 \(0<\xi<1.\)再设两侧相邻区域（按面积个数计）分别为 \(k_1\) 和 \(k_2\)，即：\(S_{\triangle PDB}=k_1/n,S_{\triangle PEC}=k_2/n,\)其中 \(k_1,k_2 \ge 0\)。
由面积比可得三条方程：
\[ n\lambda\mu=1,n(1-\lambda)\mu\xi=k_1,n\lambda(1-\mu)(1-\xi)=k_2 \]
考虑第一种情况：\(k_1=0\) 或 \(k_2=0\)。不失一般性，假设 \(k_1=0\)，这等价于 \(\lambda=1\)（切线直接经过 \(B\)），此时剩余结构完全由 \(k_2\) 决定，且 \(k_2\) 可以取 \(1,2,\dots,n-2\)，共 \(n-2\) 种。同理 \(k_2=0\) 也有 \(n-2\) 种。对固定未切顶点 \(A\)，共 \(2(n-2)\) 种；再乘上三个顶点选择，得到：\(\psi_2(n)=6(n-2).\)
再考虑第二种情况：\(k_1,k_2>0.\)令 \(x=k_1,y=k_2\)，并假设 \(x,y\ge 1\)。
由前两式与 \(n\lambda\mu=1\) 可消出 \(\mu,\xi\)，最终得到关于 \(\lambda\) 的二次方程：
\[ n(x+1)\lambda^2-(n+x+y+1)\lambda+(y+1)=0. \]
其判别式为：\(\Delta=(n+x+y+1)^2-4n(x+1)(y+1).\)展开整理后可写成：\(\Delta=(n-(2xy+x+y+1))^2-4x(x+1)y(y+1).\)因此有实根的充要条件为：\(n \ge 2xy+x+y+1+2\sqrt{x(x+1)y(y+1)}.\)
可见，若 \(\Delta<0\)，那么无解（无切法）；若 \(\Delta=0\)，那么恰一根（恰 1 种切法）；若 \(\Delta>0\)，那么两根（恰 2 种切法）并且在上述条件满足时，可见这些根都会落在合法区间内，对应合法几何切法。因此，对固定 \(x,y\)，这些子类对 \(\psi(n)\) 的贡献就是按判别式符号记 \(0/1/2\)。
令\(T(x,y)=4x(x+1)y(y+1),s=\lfloor\sqrt{T(x,y)}\rfloor,L(x,y)=2xy+x+y+1+s.\)那么：若 \(T(x,y)\) 不是完全平方数，则合法 \(n\) 从 \(L(x,y)+1\) 开始，每个 \(n\) 贡献 \(2;\)若 \(T(x,y)\) 是完全平方数，则 \(n=L(x,y)\) 时贡献 \(1\)，之后每个 \(n>L(x,y)\) 贡献 \(2\)。
令\(S=\{i^2\mid i\in\mathbb{Z}\}\)表示平方数集合。所以对固定 \((x,y)\)，在 \(n\le N\) 范围内总贡献（单个未切顶点、固定左右顺序）是：
\[ 2(N-L(x,y))+\mathbf{1}\{T(x,y)\in S\} ,(L(x,y)\le N) \]
否则为 \(0\)。再考虑对称性：未切顶点有 \(3\) 个选择，且左右交换 \((x,y)\) 在 \(x\ne y\) 时对应不同切法，因此可令 \(y\ge x\) 后乘 \(2\)（当 \(x=y\) 时只乘 \(1\)），于是：
\[ \Psi(N)=\sum_{n=3}^N\left(\binom{n-1}{2}+6(n-2)\right) +3\sum_{x\ge 1}\sum_{y\ge x}(2-\delta_{x,y})C_N(x,y), \]
其中\(\delta_{x,y}\) 为 Kronecker delta（当 \(x=y\) 时为 \(1\)，否则为 \(0\)），用于统一表示对称项计数，以及\(C_N\)为
\[ C_N(x,y)= \begin{cases} 2(N-L(x,y))+\mathbf{1}\{T(x,y)\in S\}, & L(x,y)\le N,\\ 0, & L(x,y)>N. \end{cases} \]
可见前半部分有\(\displaystyle\sum_{n=3}^N\left(\binom{n-1}{2}+6(n-2)\right)=\frac{(N+18)(N-1)(N-2)}6.\)因此得到最终表达式为：
\[ \Psi(N)=\frac{(N+18)(N-1)(N-2)}6 +3\sum_{x\ge1}\sum_{y\ge x}(2-\delta_{x,y})C_N(x,y). \]
代码
1 |
|