Project Euler 415
Project Euler 415
题目
Titanic sets
A set of lattice points \(S\) is called a titanic set if there exists a line passing through exactly two points in \(S\).
An example of a titanic set is \(S = \{(0, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 0)\}\), where the line passing through \((0, 1)\) and \((2, 0)\) does not pass through any other point in \(S\).
On the other hand, the set \(\{(0, 0), (1, 1), (2, 2), (4, 4)\}\) is not a titanic set since the line passing through any two points in the set also passes through the other two.
For any positive integer \(N\), let \(T(N)\) be the number of titanic sets \(S\) whose every point \((x, y)\) satisfies \(0 \le x, y \le N\).
It can be verified that \(T(1) = 11, T(2) = 494, T(4) = 33554178, T(111) \bmod 10^8 = 13500401\) and \(T(10^5)\bmod10^8 = 63259062\).
Find \(T(10^{11})\bmod10^8\).
解决方案
在整数格点集合\(\mathcal{G}_N=\{(x,y)\mid 0\le x,y\le N\},\)称点集 \(S\subseteq\mathcal{G}_N\) 为 titanic set，若存在一条直线 恰好穿过 \(S\) 中两个点。
若一个点集 \(S\) 不是 titanic，则对任意两点所确定的直线都至少包含第三个点，即：
- 若 \(|S|\le 1\)，显然不是 titanic；
- 若 \(|S|\ge 2\)，则“任意两点直线都包含第三点”意味着所有点必须 共线（这可以视为 Sylvester–Gallai 定理在整数格点上的一个直接推论：只要不全共线，就一定存在一条普通线只过两点）。
因此，非 titanic 集合 只有两类：空集或单点集；至少 \(3\) 个点且全部共线的集合。
于是我们只需数出“非 titanic”的数量 \(U(N)\)，则\(T(N)=2^{(N+1)^2}-U(N).\)
可见，空集、单点集的数量一共有\(1+(N+1)^2\)个。
每一条水平线含 \(N+1\) 点，总共有 \(N+1\) 条；垂直线同理，所以共有 \(2(N+1)\) 条。
在一条含 \(m=N+1\) 点的直线上，选取至少 \(3\) 个点的子集数为\(g(m)=2^m-\dbinom m0-\dbinom m1-\dbinom m2=2^m-1-m-\dfrac{m(m-1)}2.\)因此贡献：\(2(N+1)g(N+1).\)
斜率 \(+1\)（主对角）有 \(1\) 条长为 \(N+1\)，其余平行线长度从 \(1\) 到 \(N\) 各出现 \(2\) 次。斜率 \(-1\) 同理。 因此把 \(\pm 1\) 的所有对角线（两种方向）合计的“长度 \(\ge 3\) 子集数”可以写成：\(\displaystyle{2g(N+1)+4\sum_{k=3}^{N}g(k).}\)
我们令\(\displaystyle{G(N)=\sum_{k=3}^{N}g(k)=2^{N+1}-\frac{N(N+1)(N+2)}6-N-2(N\ge 3).}\)那么综合起来，上面这块简单部分可记为
现在只剩斜率既非 \(0\)、\(\infty\)、\(\pm1\) 的直线。它们可用 原始方向向量 \((a,b)\) 描述：设 \(a>b\ge 1,\gcd(a,b)=1\)，方向向量为 \((a,b)\)；若再乘以整数 \(k\ge 2\)，得到位移 \((ka,kb)\)，对应线段端点差。
当端点差为 \((ka,kb)\) 且 \(\gcd(a,b)=1\) 时，线段上整点数量为\(k+1\)（每走一步 \((a,b)\) 到下一格点，共走 \(k\) 步）。
我们需要统计：在一条包含 \(k+1\) 个格点的直线上，能够形成“至少 \(3\) 点共线集合”的选择数，并且 要避免重复计数（同一集合可能对应多个端点差）。
为处理重复，考虑一条直线上 连续 的 \(k+1\) 个格点（记为 \(0,1,\dots,k\)），我们定义 \(p(k)\) 为其中所有非法点集 \(S\) 的数量，要求：\(|S|\ge 3\)且 \(S\) 的最左点恰为 \(0\)，最右点恰为 \(k\)（即 \(S\) 的“最小覆盖线段”正好是整段 \([0,k]\)）。换句话说，\(p(k)\) 只计数那些 “最短覆盖长度恰为 \(k\)” 的共线点集，从而使每个非法集合都能被唯一归类到某一个最短线段上，避免在更长线段的统计中重复出现。
对固定的 \(a,k\)，我们希望把所有满足 \(\gcd(a,b)=1\) 的 \(b\) 的贡献累加起来。注意到摆放次数中，\((N+1-ka)\) 与 \(b\) 无关，因此只需处理\(\displaystyle{\sum_{\substack{1\le b\le a-1\\gcd(a,b)=1}} (N+1-kb).}\)
将其展开为两部分：\(\displaystyle{\sum_{\substack{1\le b\le a-1\\gcd(a,b)=1}} (N+1-kb)=\sum_{\substack{1\le b\le a-1\\gcd(a,b)=1}} (N+1)-k\sum_{\substack{1\le b\le a-1\\gcd(a,b)=1}} b.}\)
第一项显然是\(\displaystyle{\sum_{\substack{1\le b\le a-1\\gcd(a,b)=1}} (N+1)=\varphi(a)(N+1).}\) 根据欧拉函数\(\varphi(a)\)的性质，可知\(\displaystyle{\sum_{\substack{1\le b\le a-1\\gcd(a,b)=1}}b=\dfrac{a\varphi(a)}{2}.}\)因此第二项就是\(\dfrac{ka\varphi(a)}{2}\)。
代回原式，便得到\(\displaystyle{\sum_{\substack{1\le b\le a-1\\gcd(a,b)=1}} (N+1-kb)=\varphi(a)\left(N+1-\frac{ka}{2}\right).}\)
于是一般部分总贡献为：
\[ X(N)=4\sum_{k\ge2}p(k)\sum_{a\ge2,ka\le N}\varphi(a)(N+1-ka)\left(N+1-\frac{ka}{2}\right). \]
设 \(n=N+1\)。展开括号得到：\((N+1-ka)\left(N+1-\dfrac{ka}{2}\right)=n^2-\dfrac{3n}{2}(ka)+\dfrac12 (ka)^2.\)
因此\(\displaystyle{X(N)=4\left(n^2S_0-\frac{3n}{2}S_1+\frac12S_2\right),}\)其中\(\displaystyle{S_0=\sum_{\substack{k\ge 2,a\ge2\\ka\le N}}p(k)\varphi(a),S_1=\sum_{\substack{k\ge 2,a\ge2\\ka\le N}}kap(k)\varphi(a),S_2=\sum_{\substack{k\ge 2,a\ge2\\ka\le N}}k^2a^2p(k)\varphi(a).}\)
由于这里只统计斜率 \(0<\dfrac ba<1\) 的“斜线段族”，因此枚举变量满足 \(k\ge2,a\ge2\)；等价地，\(p(1)=0\)是成立的，并对所有 \(\Phi_i\) 统一减去 \(\varphi(1)\cdot 1^i=1\)，从而尝试直接使用标准的Dirichlet 双曲线方法。
令 \(f_i(k)=k^i p(k),g_i(a)=a^i\varphi(a)\)，则记\(\displaystyle{F_i(x)=\sum_{k\le x}f_i(k),\Phi_i(x)=\sum_{a\le x}g_i(a)}\)这些是 欧拉函数的加权前缀和，因此只要能快速得到：\(\Phi_0,\Phi_1,\Phi_2\)的函数值，就能计算 \(S_0,S_1,S_2\)。那么由Dirichlet 双曲线方法可以得到：
\[ \sum_{ka\le N}f_i(k)g_i(a) =\sum_{k\le \sqrt N}f_i(k)\Phi_i\left(\left\lfloor\frac Nk\right\rfloor\right) +\sum_{a\le \sqrt N}g_i(a)\Phi_i\left(\left\lfloor\frac Na\right\rfloor\right) -F_i(\sqrt N)\Phi_i(\sqrt N), \]
随后我们在后面令\(G_i(n)=\Phi_i(n)-1\)，并在计算时去除\(a=1\)的情况即可。
我们令幂和\(\displaystyle{T_i(n)=\sum_{k=1}^n k^i}\)。那么有\(T_0(n)=n,T_1(n)=\dfrac{n(n+1)}{2},T_2(n)=\dfrac{n(n+1)(2n+1)}{6},T_3(n)=\left(\dfrac{n(n+1)}{2}\right)^2\)。可见，对于\(F_i(i=0,1,2)\)的计算结果如下：
\[ \begin{aligned} F_0(n)&=\sum_{k=1}^np(k)\\ &=2^n-n-1,\\ F_1(n)&=\sum_{k=1}^nkp(k)\\ &=\sum_{k=1}^{x}k2^{k-1}-T_1(n)\\&=2^n(n-1)-\dfrac{n(n+1)}{2}+1.\\ F_2(n)&=\sum_{k=1}^nk^2p(k)\\ &=\sum_{k=1}^{x}k^22^{k-1}-T_2(n)\\ &=(n^2-2n+3)2^n-\frac{n(n+1)(2n+1)}6-3 \end{aligned} \]
接下来我们求解\(\Phi_i(n)\)。欧拉函数有性质：\(\displaystyle\sum_{d\mid n}\varphi(d)=n.\)，那么两侧同乘\(n^i\)，并且级数每项分子分母各乘上一个\(d^i\)，可得\(\displaystyle{\sum_{d\mid n} d^i\left(\frac{n}{d}\right)^i\varphi\left(\frac{n}{d}\right)=n^{i+1}.}\)这等价于一个 Dirichlet 卷积恒等式：
\[ (n^i) \ast (n^i\varphi(n)) = n^{i+1}. \]
对上式在 \(1\le n\le x\) 求和，那么有
\[T_{i+1}(x)=\sum_{n\le x}n^{i+1}=\sum_{n\le x}\sum_{d\mid n} d^i\left(\frac{n}{d}\right)^i\varphi\left(\frac{n}{d}\right)=\sum_{d\le x} d^i \sum_{m\le x/d} m^i\varphi(m)=\sum_{d\le x} d^i\Phi_i\left(\left\lfloor\frac{x}{d}\right\rfloor\right).\]
上式中 \(d=1\) 的项就是 \(\Phi_i(x)\)，因此
\[ \Phi_i(x)=T_{i+1}(x)-\sum_{d=2}^{x} d^i\Phi_i\left(\left\lfloor\frac{x}{d}\right\rfloor\right). \]
注意到 \(\left\lfloor\dfrac{x}{d}\right\rfloor < x\)（当 \(d\ge2\)），这就是一个“严格变小”的递推，配合记忆化就能算所有需要的 \(\Phi_i(\cdot)\)。 可见，递推中出现的关键结构是\(\displaystyle{\sum_{d=2}^{x} d^i\Phi_i\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}\)也就是说\(\Phi_i\)可以使用数论分块求解。设\(q=\left\lfloor\dfrac{x}{d}\right\rfloor,\)那么当 \(q\) 固定时，\(d\) 会落在一个连续区间\(L_q=\left\lfloor\dfrac{x}{q+1}\right\rfloor+1 \le d \le \left\lfloor\dfrac{x}{q}\right\rfloor=R_q.\)
因此可以把递推写成按 \(q\) 分块的形式：
\[ \sum_{d=2}^{x} d^i\Phi_i\left(\left\lfloor\frac{x}{d}\right\rfloor\right) =\sum_{q=1}\Phi_i(q)\sum_{d= L_q}^{R_q} d^i =\sum_{q=1}\Phi_i(q)(T_i(R_q)-T_i(L_q-1)), \]
其中对于\(T_i\)我们回代上文所提到的\(T_0,T_1,T_2,T_3\)即可。令\(U(N)=C(N)+X(N),\)则答案为
\[ T(N)= 2^{(N+1)^2}-U(N) \]
代码
1 |
|