Day 179-Q1 — 2026-10-15 | 引く倍数に下限 L と上限 K のあるユークリッドゲームの和（鎖は周期 L+K。先頭の値 x の区画が「列の先頭 1 個＋末尾 s−1 個」に分かれる形を読み取り、勝ち手の数を区間の数え上げで出す）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n, L, K = int(data[0]), int(data[1]), int(data[2])
    P = L + K                      # 鎖の周期
    M = (P - 1) // L               # 値の最大
    last = P - M * L               # 値 M の区画の長さ（1..L）
    ML = M * L

    def size(v):                   # 基本列で値 v が占める長さ
        return L if v < M else last

    def h(t, x):                   # 鎖の t 番目（0 <= t < P）、先頭の値が x
        if x == 0:
            return min(t // L, M)
        if t == 0:
            return x
        p = t - 1
        if p < x * L:
            return p // L
        sx = size(x)
        if p < P - sx:
            return min((p + sx) // L, M)
        return x

    def spans(T, x):               # 1 周期のうち値 T を取る区間 [l, r) のリスト
        if T > M:
            return ()
        if x == 0:
            return ((T * L, T * L + size(T)),)
        sx = size(x)
        if T == x:
            return ((0, 1), (P - sx + 1, P))
        if T < x:
            return ((T * L + 1, T * L + L + 1),)
        return ((T * L - sx + 1, T * L + size(T) - sx + 1),)

    def prefix(T, x, m):           # 0 <= j < m で h_j == T の個数
        sp = spans(T, x)
        whole, rest = divmod(m, P)
        c = 0
        for l, r in sp:
            c += whole * (r - l)
            if rest > l:
                c += min(rest, r) - l
        return c

    gs = []
    info = []
    for i in range(n):
        a = int(data[3 + 2 * i])
        b = int(data[4 + 2 * i])
        if a < b:
            a, b = b, a
        qs = []
        while b:
            qs.append(a // b)
            a, b = b, a % b
        x = 0                      # (d, 0) は終局で値 0
        for k in range(len(qs) - 1, 0, -1):   # h を手で展開（呼び出しを省く）
            t = qs[k] % P
            if x == 0:
                x = t // L if t < ML else M
            elif t:
                p = t - 1
                if p < x * L:
                    x = p // L
                else:
                    sx = L if x < M else last
                    if p < P - sx:
                        p += sx
                        x = p // L if p < ML else M
        q = qs[0]
        gs.append(h(q % P, x))
        info.append((q, x))
    G = 0
    for g in gs:
        G ^= g
    if G == 0:
        print("Second")
        print(0)
        return
    cnt = 0
    for g, (q, x) in zip(gs, info):
        if q < L:
            continue               # この組では手が無い
        T = G ^ g
        lo = q - K if q > K else 0  # 行き先の鎖の添字 [lo, q-L]
        cnt += prefix(T, x, q - L + 1) - prefix(T, x, lo)
    print("First")
    print(cnt)


main()