题目分析（假设为时间调度问题）

该代码用于求解满足特定约束条件的最小时间长度 ( L )，涉及同余方程和扩展欧几里得算法。每个任务有开始时间 ( ci[i] )、周期 ( pi[i] ) 和最长等待时间 ( li[i] )，需确保所有任务在时间区间内无冲突。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 22;
LL ci[maxn], pi[maxn], li[maxn], n;

// 扩展欧几里得算法求ax + by = gcd(a,b)的解
void exgcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if (b == 0) d = a, x = 1, y = 0;
    else {
        exgcd(b, a % b, d, y, x);
        y -= (a / b) * x;
    }
}

// 检查当前L是否满足所有约束条件
bool check(LL L) {
    for (LL i = 1; i <= n; i++) {
        for (LL j = i + 1; j <= n; j++) {
            LL A, B, d, X, Y, K;
            A = pi[j] - pi[i]; A = (A + L) % L;  // 周期差模L
            B = L;
            K = ci[i] - ci[j]; K = (K + L) % L;  // 开始时间差模L
            exgcd(A, B, d, X, Y);
            if (K % d != 0) continue;  // 方程无解，跳过
            LL dx = abs(B / d);  // 解的周期
            X = X * (K / d);
            X = (X % dx + dx) % dx;  // 最小非负解
            if (X <= li[i] && X <= li[j]) return false;  // 存在冲突
        }
    }
    return true;
}

int main() {
    scanf("%lld", &n);
    LL L = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld", &ci[i], &pi[i], &li[i]);
        L = max(L, ci[i]);  // 初始L设为最大开始时间
    }
    while (check(L) == false) L++;  // 寻找最小L
    printf("%lld\n", L);
    return 0;
}

思路说明

1. 问题核心：需找到最小 ( L )，使得所有任务在时间区间 ([0, L)) 内无冲突。
2. 冲突检测：对任意两任务 ( i, j )，通过同余方程 ( (pi[j]-pi[i])X \equiv (ci[i]-ci[j]) \mod L ) 判断是否存在冲突时间 ( X )。若存在且 ( X \leq li[i], li[j] )，则 ( L ) 需增大。
3. 扩展欧几里得：用于求解同余方程，判断解是否存在及最小非负解。
4. 二分优化：从初始 ( L )（最大开始时间）开始，逐步增大 ( L ) 直至满足所有约束。