Codeforces 194B 詳解

題目：n×n 方格，從左下角開始，每次走 n+1 格畫一個叉。問回到起點時共畫了多少個叉。

核心數學：環上步長與 GCD

總格子數 N = n²。但實際移動在「邊界」上？題目實際模型：
考慮邊長 4n 的正方形周長（或等價環）。每步移動 n+1。
回到起點需步數 k 滿足 k·(n+1) ≡ 0 (mod 4n)。
最小正 k = 4n / gcd(4n, n+1)。
叉數 = 步數 + 1（含起點）。

推導簡化

gcd(4n, n+1) = gcd(4n - 4(n+1), n+1) = gcd(-4, n+1) = gcd(4, n+1)。
故 k = 4n / gcd(4, n+1)。
叉數 = k + 1 = 4n / gcd(4, n+1) + 1。

參考代碼 (C++ / Python)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        long long n; cin >> n;
        long long g = std::gcd(4LL, n+1);
        cout << 4*n/g + 1 << '\n';
    }
    return 0;
}

import math, sys
def solve():
    data = sys.stdin.read().split()
    if not data: return
    t = int(data[0])
    out = []
    for i in range(1, t+1):
        n = int(data[i])
        g = math.gcd(4, n+1)
        out.append(str(4*n//g + 1))
    sys.stdout.write('\n'.join(out))
if __name__ == '__main__':
    solve()

關鍵測試

複雜度分析

總結

CF 194B 是純數學題。關鍵在於建立正確模型：周長 4n，步長 n+1，求最小正整數 k 使 k·(n+1) ≡ 0 (mod 4n)。利用 GCD 性質化簡 gcd(4n, n+1) = gcd(4, n+1)，得出 O(1) 公式。此類「環上行走、周期性、GCD」問題在數論、密碼學、信號處理中極常見。