寻求高效计算Farey序列长度的算法 解决CodinGame谜题

谜题描述 #

想象一个n×n的方格城市，每个单元格中心（除中心格外）都有一栋建筑，总计n×n - 1栋。所有建筑都是极小的圆形，规格完全一致。

某天你站在城市中心散步，从这里能看到许多建筑，但并非全部——同方向的建筑会互相遮挡。请问你能看到多少栋建筑？

输入：一个奇数n（1 < n < 10000000）
输出：可见建筑的数量

示例：当n=7时，输出为32（@代表中心，**#**代表可见建筑，_代表不可见建筑）：

_ **#** **#** _ **#** **#** _
**#** _ **#** _ **#** _ **#**
**#** **#** **#** **#** **#** **#** **#**
_ _ **#** @ **#** _ _
**#** **#** **#** **#** **#** **#** **#**
**#** _ **#** _ **#** _ **#**
_ **#** **#** _ **#** **#** _

测试用例 #

我的尝试 #

我独立发现最终结果必能被8整除，因此只需计算城市1/8区域内的可见建筑数再乘以8。设中心为(0,0)，该区域内的可见建筑数等于满足以下条件的点(x,y)的数量：

• 1 ≤ x < y < N = (n + 1) / 2，且
• x和y的最大公约数（gcd）为1

经过搜索，我发现该问题属于法雷太阳图（Farey sunburst）范畴。我将维基百科上的迭代Python实现改写为JavaScript版本，它能通过前4个测试用例（n ≤ 33），但在n=999999时超时：

const f = n => {
    let s = 0;
    let [i, j, k, l] = [0n, 1n, 1n, n];

    while (k <= n) {
        let t = (n + j) / l | 0n;
        [i, j, k, l] = [k, l, t * k - i, t * l - j];
        s++;
    }

    return s;
};

随后我找到公式：

|Fₙ| = |Fₙ₋₁| + phi(n)

其中Fₙ是第n阶法雷序列，phi(n)是欧拉函数，表示1到n中与n互质的数的个数。我据此实现了代码：

const gcd = (a, b) => {
    while (b) {
        [a, b] = [b, a % b];
    }
    return a;
};

const phi = n => {
    let s = 0;
    for (let i = 1; i <= n; i++) {
        s += gcd(n, i) === 1;
    }
    return s;
};

const f = n => {
    let s = 1;
    for (let i = 2; i <= n; i++) {
        s += phi(i);
    }
    return s;
};

由于该实现的时间复杂度为O(n²)，无法通过n=999999的测试用例。

感谢他人提示，我使用了优化后的欧拉函数phi实现，它能通过多数测试用例，但在n=9999999时耗时约7.6秒，超出了时间限制：

const phi = n => {
    let s = n;

    for (let i = 2; i ** 2 <= n; i++) {
        if (!(n % i)) {
            while (!(n % i)) {
                n = n / i | 0;
            }
            s -= s / i | 0;
        }
    }

    if (n > 1) {
        s -= s / n | 0;
    }

    return s;
};

环境限制 #

代码运行在64位多核Linux环境中，内存限制为768MB，测试显示时间限制约为6秒。

附注：我也看过相关问题，但其中提供的函数对我的场景来说仍然太慢。

请问：我需要哪种算法来解决这个谜题？

内容的提问来源于stack exchange，提问作者InSync