lessons/互动程序/10-高斯消元与CRT/00-开关与错开的时钟.py

#!/usr/bin/env python3
"""课前零食：追踪 XOR 高斯消元与非互质 CRT 合并。"""

from __future__ import annotations

from math import gcd


MATRIX = [
    [1, 1, 0, 1],  # x1 xor x2 = 1
    [0, 1, 1, 0],  # x2 xor x3 = 0
    [1, 0, 1, 1],  # x1 xor x3 = 1（依赖前两行）
]


def ask(prompt: str, default: str) -> str:
    try:
        return input(prompt).strip() or default
    except EOFError:
        return default


def print_matrix(matrix: list[list[int]]) -> None:
    for row in matrix:
        print("  ", " ".join(map(str, row[:-1])), "|", row[-1])


def xor_lab() -> None:
    matrix = [row[:] for row in MATRIX]
    variables = len(matrix[0]) - 1
    pivot_row = 0
    print("\n增广矩阵（最后一列为右侧常数）：")
    print_matrix(matrix)
    for column in range(variables):
        pivot = next((r for r in range(pivot_row, len(matrix)) if matrix[r][column]), None)
        if pivot is None:
            print(f"第 {column + 1} 列没有主元：对应变量暂时自由。")
            continue
        matrix[pivot_row], matrix[pivot] = matrix[pivot], matrix[pivot_row]
        print(f"\n选第 {column + 1} 列主元，放到第 {pivot_row + 1} 行。")
        for row in range(len(matrix)):
            if row != pivot_row and matrix[row][column]:
                matrix[row] = [a ^ b for a, b in zip(matrix[row], matrix[pivot_row])]
                print(f"  第 {row + 1} 行 XOR 主元行")
        print_matrix(matrix)
        pivot_row += 1
    contradiction = any(not any(row[:-1]) and row[-1] for row in matrix)
    print("\n秩 =", pivot_row)
    if contradiction:
        print("出现 0=1：无解。")
    elif pivot_row < variables:
        print("相容但有自由变量：多解。")
    else:
        print("每个变量有主元：唯一解。")


def exgcd(a: int, b: int) -> tuple[int, int, int]:
    if b == 0:
        return a, 1, 0
    g, x, y = exgcd(b, a % b)
    return g, y, x - (a // b) * y


def merge(a: int, m: int, b: int, n: int) -> tuple[int, int] | None:
    g = gcd(m, n)
    print(f"gcd({m},{n})={g}，差 b-a={b - a}")
    if (b - a) % g:
        return None
    reduced_m, reduced_n = m // g, n // g
    _, inverse, _ = exgcd(reduced_m, reduced_n)
    t = ((b - a) // g * inverse) % reduced_n
    modulus = m * reduced_n
    value = (a + m * t) % modulus
    print(f"解出 t={t}，所以 x={value} (mod {modulus})")
    return value, modulus


def crt_lab() -> None:
    raw = ask("输入 a m b n（回车为 1 4 3 6）： ", "1 4 3 6")
    try:
        a, m, b, n = map(int, raw.split())
        if m <= 0 or n <= 0:
            raise ValueError
    except ValueError:
        print("格式应为四个整数 a m b n；使用预设。")
        a, m, b, n = 1, 4, 3, 6
    print(f"\n合并 x≡{a} (mod {m}) 与 x≡{b} (mod {n})")
    result = merge(a, m, b, n)
    if result is None:
        print("不兼容：两只时钟永远不会同时指向这些余数。")
    else:
        value, modulus = result
        print(f"验算：{value}%{m}={value % m}，{value}%{n}={value % n}；以后每隔 {modulus} 重复。")


def main() -> None:
    choice = ask("选择 x=XOR 消元，c=CRT 合并（回车为 x）： ", "x").lower()
    if choice == "c":
        crt_lab()
    else:
        xor_lab()


if __name__ == "__main__":
    main()