本文介绍如何在 o(n log n) 时间内快速计算法里序列长度，核心是利用埃拉托斯特尼筛法批量预处理所有欧拉函数值，从而解决大规模（n ≤ 5×10⁶）下的可见建筑计数问题。
本文介绍如何在 o(n log n) 时间内快速计算法里序列长度，核心是利用埃拉托斯特尼筛法批量预处理所有欧拉函数值，从而解决大规模（n ≤ 5×10⁶）下的可见建筑计数问题。
该问题本质是求法里序列 FN 的项数（不含 0/1 和 1/1 的严格定义下，常取 |FN| = 1 + Σi=1N φ(i)），而“城市中心可见建筑数”恰好等价于 8 × (|FN| − 2)，其中 N = (n+1)/2。这是因为对称性将可视方向压缩至第一象限中满足 0 N 中介于 0 和 1 之间的项数减 1）。
直接逐个计算 φ(i)（即使使用试除优化版）仍为 O(N√N)，在 n ≈ 10⁷ 时 N ≈ 5×10⁶，必然超时。正确解法是批量筛法预处理：不分解每个数，而是用类似埃氏筛的方式，对每个质数 p，遍历其所有倍数 j，并累计更新两个辅助数组：
- P[j]：记录 j 的所有不同质因数乘积（即 rad(j)，根函数）；
- Q[j]：记录 j 的所有不同质因数分别减 1 后的乘积。
由欧拉函数公式 φ(j) = j × Πp∣j (p−1)/p = j × Q[j] / P[j]，即可 O(1) 得到任意 φ(j)。
以下是完整、可直接提交的 JavaScript 实现（已适配 CodinGame 环境，含输入读取与大数安全整数运算）：
const n = +readline();
const N = Math.floor((n + 1) / 2); // 注意：n 为奇数，N 为整数
// 边界处理：当 n === 1 时 N === 1，但题设 n > 1，故 N ≥ 2
const size = N + 1;
const P = new Array(size).fill(1); // P[i] = ∏_{p|i} p
const Q = new Array(size).fill(1); // Q[i] = ∏_{p|i} (p-1)
// 埃氏筛变体：仅需遍历到 N
for (let i = 2; i {
const pVal = P[x];
return Math.floor(x / pVal) * Q[x]; // 等价于 (x * Q[x]) / P[x]，但规避大数精度丢失
};
// 计算 |F_N| = 1 + Σ_{i=1}^N φ(i)
// 注意：标准 Farey 序列 F_N 包含 0/1 和 1/1，共 1 + Σ_{i=1}^N φ(i) 项
// 而本题中，八分之一区域对应的是满足 1≤x<y gcd n="(n+1)/2，答案" let sumphi="0;" for i="1;" phi console.log><p><strong>关键注意事项：</strong> </p>
<ul>
<li>数组大小必须为 N+1（索引 0..N），避免越界； </li>
<li>phi(1) = 1，务必包含在求和中； </li>
<li>减去的 2 来源于 Farey 序列中 0/1 和 1/1 两个端点不贡献可视方向，经几何对称性推导后恰好对应八分之一扇形内的有效互质对数量； </li>
<li>所有运算使用 Math.floor 和整数乘除，避免 JavaScript 浮点数对大整数（如 60792708184960）的精度丢失； </li>
<li>时间复杂度 O(N log log N)（筛法主循环），空间复杂度 O(N)，完全满足 n ≤ 10⁷ 的约束（此时 N ≤ 5×10⁶，内存占用约 80 MB）。</li>
</ul>
<p>此方法将原本 O(N²) 的暴力解法提升至近线性，是解决大规模 Farey 相关计数问题的标准范式。</p></y>
