NYOJ 145 聰明的小珂：最大步長 k 使環狀遍歷覆蓋所有項鏈

NYOJ 145 - 最大步長 k 使 n 項鏈環狀遍歷恰好覆蓋所有

n 條項鏈圍成圈，每次從上一個位置順時針數 k 步取項鏈。求最大 k ≤ n/2 使得 n 天內每條項鏈恰好取一次。n < 2^31。

數學本質

序列：1, 1+k, 1+2k, ... (mod n)。要恰好遍歷所有 n 個位置，等價於 k 與 n 互質（gcd(n,k)=1）。因若 gcd=d>1，則只能訪問 n/d 個位置。

解法

從 n/2 向下枚舉 k，第一個滿足 gcd(n,k)=1 的即為答案。n < 2^31，gcd 為 O(log n)，最多枚舉 n/2 次，但實際上互質數密度 ~6/π^2 ≈ 0.6，極快找到。

代碼

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int main() {
    int m, n; scanf("%d", &m);
    while (m--) {
        scanf("%d", &n);
        for (int k = n/2; k >= 1; --k)
            if (gcd(n, k) == 1) { printf("%d\n", k); break; }
    }
    return 0;
}

樣例

n=7：k=3（gcd=1），序列 1,4,7,3,6,2,5 覆蓋所有。k=2 也互質但非最大。

複雜度

平均 O(log n) 找到答案，最壞 O(n log n) 但實際極快。m < 10000 總時間安全。