zhoujinchong2004 @ 2025-10-22 18:48:14

一、问题数学建模

1.1 问题本质

这是一个周期性函数统计问题，核心在于找到数对 $(x, y)$ 的循环周期，然后在多个区间内统计不重复的数对个数。

数学形式化

给定：

时间 $t \in [0, 10^{18}]$
显示函数：$$x(t) = \left(t + \left\lfloor \frac{t}{B} \right\rfloor\right) \bmod A $$ $y(t) = t \bmod B$
$n$ 个工作时间区间 $[l_i, r_i]$

求：不同数对 $(x, y)$ 的个数。

1.2 暴力算法的困境

直接枚举：

set<pair<int,int>> unique_pairs;
for (每个区间 [l, r]) {
    for (ll t = l; t <= r; t++) {
        ll x = (t + t/B) % A;
        ll y = t % B;
        unique_pairs.insert({x, y});
    }
}
return unique_pairs.size();

复杂度分析：

区间总长度 $S = \sum (r_i - l_i + 1)$ 最大可达 $10^{18}$
时间复杂度： $O(S)$ ❌ 必然超时

突破口：寻找数对的周期性规律！

二、核心数学理论

2.1 关键观察： $y$ 的周期性

命题 1： $y(t)$ 的周期为 $B$ 。

证明：

y(t + B) = (t + B) \bmod B = t \bmod B = y(t)

因此 $y$ 以 $B$ 为周期循环，取值范围为 $\{0, 1, 2, \ldots, B-1\}$ 。

2.2 关键推导： $x$ 的周期性

定理 1： $x(t)$ 的表达式变换

引理：设 $t = kB + r$ ，其中 $0 \le r < B$ ，则：

x(t) = \left(k(B+1) + r\right) \bmod A

证明：

$$\begin{aligned} x(t) &= \left(t + \left\lfloor \frac{t}{B} \right\rfloor\right) \bmod A \\ &= \left(kB + r + \left\lfloor \frac{kB + r}{B} \right\rfloor\right) \bmod A \\ &= \left(kB + r + k\right) \bmod A \\ &= \left(k(B+1) + r\right) \bmod A \end{aligned} $$

物理意义：

当 $t$ 每增加 $B$ （即 $y$ 循环一周）， $k$ 增加 $1$
此时 $x$ 增加 $(B+1) \bmod A$

定理 2： $(x, y)$ 的整体周期

命题 2：数对 $(x, y)$ 的最小正周期为：

T = \text{lcm}(A, B+1)

证明要点：

$y$ 的周期： $B$ （显然）
$x$ 在模 $B$ 意义下的周期：
- 固定 $r \in [0, B-1]$ ，考虑 $t = kB + r$
- $x(t) = k(B+1) + r \pmod{A}$
- 当 $k$ 增加 $\Delta k$ 时， $x$ 增加 $\Delta k \cdot (B+1) \pmod{A}$
- 要使 $x$ 回到原值，需要 $\Delta k \cdot (B+1) \equiv 0 \pmod{A}$
- 最小的 $\Delta k = \frac{A}{\gcd(A, B+1)}$
- 对应的时间周期为 $\Delta k \cdot B = \frac{AB}{\gcd(A, B+1)}$
整体周期：
$T = \frac{AB}{\gcd(A, B+1)} = \text{lcm}(A, B+1)$

推论：在一个完整周期 $[0, T-1]$ 内，恰好包含所有可能的不同数对 $(x, y)$ 。

2.3 周期内不同数对的个数

定理 3：一个完整周期内不同数对的个数等于周期长度 $T$ 。

证明：

由于 $(x, y)$ 的映射关系：

$y = t \bmod B$ 确定了 $t$ 在哪个" $B$ 块"内的位置
$x = (t + \lfloor t/B \rfloor) \bmod A$ 确定了具体是哪个块

单射性：对于 $t_1, t_2 \in [0, T-1]$ ，如果 $t_1 \neq t_2$ ，则 $(x(t_1), y(t_1)) \neq (x(t_2), y(t_2))$ 。

证明单射性：

假设 $(x(t_1), y(t_1)) = (x(t_2), y(t_2))$
则 $y(t_1) = y(t_2) \implies t_1 \equiv t_2 \pmod{B}$
设 $t_1 = k_1 B + r, t_2 = k_2 B + r$
则 $x(t_1) = x(t_2) \implies k_1(B+1) + r \equiv k_2(B+1) + r \pmod{A}$
即 $(k_1 - k_2)(B+1) \equiv 0 \pmod{A}$
由于 $t_1, t_2 \in [0, T-1]$ ，有 $|k_1 - k_2| < \frac{A}{\gcd(A, B+1)}$
只有 $k_1 = k_2$ 时成立，因此 $t_1 = t_2$

因此映射是单射，一个周期内恰有 $T$ 个不同的数对。□

三、算法设计思路

3.1 核心策略：周期归约

关键思想：将所有时间区间模周期 $T$ ，转化为 $[0, T-1]$ 内的区间问题。

算法框架：

计算周期 $T = \text{lcm}(A, B+1)$
检查是否存在长度 $\ge T$ 的区间（直接返回 $T$ ）
将每个区间 $[l_i, r_i]$ 转化为模 $T$ 后的区间
合并区间，统计覆盖的时刻总数

3.2 区间模运算的处理

问题：区间 $[l, r]$ 模 $T$ 后可能不连续。

示例：

$T = 10, [l, r] = [8, 12]$
$[8, 12] \bmod 10 = \{8, 9, 0, 1, 2\}$
分裂为两段： $[8, 9]$ 和 $[0, 2]$

处理规则：

if (l % T <= r % T) {
    // 情况1：模运算后仍连续
    区间 = [l % T, r % T]
} else {
    // 情况2：跨越边界，分裂为两段
    区间1 = [l % T, T - 1]
    区间2 = [0, r % T]
}

数学依据：

$$[l, r] \bmod T = \begin{cases} [l \bmod T, r \bmod T] & \text{if } l \bmod T \le r \bmod T \\ [l \bmod T, T-1] \cup [0, r \bmod T] & \text{otherwise} \end{cases} $$

四、算法流程详解

4.1 模块 1：周期计算

模块功能：计算数对 $(x, y)$ 的循环周期 $T = \text{lcm}(A, B+1)$ 。

输入参数： $A, B$ （可能达到 $10^{18}$ ）

输出：周期 $T$

实现思路：

由于 $A, B$ 很大，直接计算 $\text{lcm}(A, B+1) = \frac{A \cdot (B+1)}{\gcd(A, B+1)}$ 可能溢出。

优化策略：

使用 __int128 临时存储乘法结果
如果 $T > 10^{18}$ ，直接设为 $10^{18}$ （因为 $t$ 的范围不超过 $10^{18}$ ）

// 计算最大公约数
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 计算周期
ll compute_period(ll A, ll B) {
    __int128 val = (__int128)A * B / gcd(A, B + 1);
    
    // 防止溢出
    if (val > 1e18) {
        return 1e18;
    }
    return (ll)val;
}

关键点：

使用 __int128 避免中间计算溢出
$B+1$ 可能溢出，但在 gcd 中会自动取模
周期超过 $10^{18}$ 时截断（实际意义：区间不可能跨越完整周期）

4.2 模块 2：快速判断

模块功能：检查是否存在长度 $\ge T$ 的区间。

优化原理：

如果某个区间 $[l_i, r_i]$ 的长度 $r_i - l_i + 1 \ge T$
则这个区间必然包含一个完整周期
一个完整周期包含所有 $T$ 个不同的数对
答案直接为 $T$ ，无需继续处理

for (int i = 1; i <= n; i++) {
    ll L, R;
    cin >> L >> R;
    
    // 快速判断
    if (R - L + 1 >= T) {
        cout << T << endl;
        return 0;
    }
    
    // 否则继续处理...
}

时间节省：对于子任务中 $L$ 很大的情况，直接跳过后续复杂计算。

4.3 模块 3：区间归约

模块功能：将原始区间 $[l, r]$ 模 $T$ ，转化为 $[0, T-1]$ 内的一个或两个区间。

输入：区间 $[L, R]$ ，周期 $T$

输出：区间数组（可能包含 1 或 2 个区间）

实现逻辑：

struct Interval {
    ll l, r;
};

vector<Interval> intervals;

for (int i = 1; i <= n; i++) {
    ll L, R;
    cin >> L >> R;
    
    ll l_mod = L % T;
    ll r_mod = R % T;
    
    if (l_mod <= r_mod) {
        // 情况1：连续区间
        intervals.push_back({l_mod, r_mod});
    } else {
        // 情况2：跨越边界，分裂
        intervals.push_back({l_mod, T - 1});
        intervals.push_back({0, r_mod});
    }
}

图示说明：

周期 T = 10

原区间 [8, 12]:
    模运算: 8, 9, 10%10=0, 11%10=1, 12%10=2
    分裂为: [8, 9] ∪ [0, 2]

原区间 [3, 7]:
    模运算: 3, 4, 5, 6, 7
    保持: [3, 7]

4.4 模块 4：区间合并

模块功能：合并重叠的区间，统计覆盖的总时刻数。

算法：经典的区间合并问题。

步骤：

排序：按左端点排序

sort(intervals.begin(), intervals.end(), 
     [](Interval a, Interval b) { return a.l < b.l; });

贪心合并：

ll ans = 0;

for (int i = 0; i < intervals.size(); ) {
    ll left = intervals[i].l;
    ll right = intervals[i].r;
    
    // 尽可能向右扩展
    int j = i;
    while (j + 1 < intervals.size() && 
           intervals[j + 1].l <= right) {
        right = max(right, intervals[j + 1].r);
        j++;
    }
    
    // 累加当前合并后区间的长度
    ans += right - left + 1;
    
    // 跳到下一个未处理的区间
    i = j + 1;
}

正确性：

排序后，区间按左端点递增
贪心策略：当前区间尽可能向右延伸，能合并的都合并
每个时刻最多被统计一次

复杂度：

排序： $O(n \log n)$
扫描： $O(n)$
总复杂度： $O(n \log n)$

五、完整算法流程

流程图

输入 n, A, B
    ↓
计算周期 T = lcm(A, B+1)
    ↓
读入区间 [l_i, r_i]
    ↓
检查：是否存在 r_i - l_i + 1 >= T ?
    ↓ 是
   输出 T
    ↓ 否
将每个区间模 T（可能分裂）
    ↓
对所有区间按左端点排序
    ↓
贪心合并重叠区间
    ↓
累加合并后的区间长度
    ↓
输出答案

伪代码框架

int main() {
    // 模块1: 计算周期
    ll T = compute_period(A, B);
    
    // 模块2: 快速判断
    for (区间 [L, R]) {
        if (R - L + 1 >= T) {
            输出 T;
            return;
        }
    }
    
    // 模块3: 区间归约
    vector<Interval> intervals;
    for (区间 [L, R]) {
        将 [L, R] 模 T 后加入 intervals;
    }
    
    // 模块4: 区间合并
    sort(intervals);
    ll ans = merge_and_count(intervals);
    
    // 输出答案
    cout << ans;
}

六、复杂度分析

时间复杂度

模块	操作	复杂度
模块1	计算 GCD	$O(\log \min(A, B))$
模块2	读入并检查	$O(n)$
模块3	区间转换	$O(n)$
模块4	排序 + 合并	$O(n \log n)$

总时间复杂度： $O(n \log n)$

数值估算：

$n \le 10^6$ ， $n \log n \approx 2 \times 10^7$
可以轻松通过

空间复杂度

区间数组： $O(2n)$ （最多分裂成两倍）
其他辅助变量： $O(1)$

总空间复杂度： $O(n)$

七、数学理论深化

定理 4：数对个数的上界

命题：在任意时间范围内，不同数对的个数不超过 $\min(AB, T)$ 。

证明：

$(x, y)$ 的取值范围： $x \in [0, A-1], y \in [0, B-1]$
笛卡尔积：最多 $A \times B$ 种组合
但由于周期性，实际最多 $T = \text{lcm}(A, B+1)$ 种
因此上界为 $\min(AB, T)$

实际意义：

当 $T < AB$ 时，并非所有 $(x, y)$ 组合都能出现
例如样例1： $A = B = 3$ ， $T = 6 < 9$ ，只有 4 种数对出现

定理 5：周期的紧性

命题： $T = \text{lcm}(A, B+1)$ 是最小正周期。

证明要点：

假设存在更小的周期 $T' < T$
则 $(x(t), y(t)) = (x(t + T'), y(t + T'))$ 对所有 $t$ 成立
特别地， $y(0) = y(T') \implies T' \equiv 0 \pmod{B}$
设 $T' = kB$ ，则 $x(0) = x(T') \implies k(B+1) \equiv 0 \pmod{A}$
最小的 $k = \frac{A}{\gcd(A, B+1)}$
因此 $T' = \frac{AB}{\gcd(A, B+1)} = T$ ，矛盾

所以 $T$ 是最小正周期。□

八、算法优化技巧

优化 1：避免溢出

// ❌ 错误：可能溢出
ll T = A * B / gcd(A, B + 1);

// ✅ 正确：使用更大的数据类型
__int128 val = (__int128)A * B / gcd(A, B + 1);
ll T = (val > 1e18) ? 1e18 : (ll)val;

优化 2：快速 I/O

// 关闭同步流
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

效果：对于 $n = 10^6$ 的数据，能节省约 50% 的 I/O 时间。

优化 3：in-place 排序

// 使用 lambda 表达式简化
sort(A + 1, A + tot + 1, [](nn a, nn b) { 
    return a.l < b.l; 
});

九、易错点提醒

易错点 1： $B+1$ 的溢出

// ❌ 错误：B = 10^18 时，B+1 溢出
ll T = lcm(A, B + 1);

// ✅ 正确：gcd 函数内部会处理
ll T = A * B / gcd(A, B + 1);  // gcd 处理溢出

易错点 2：区间分裂判断

// ❌ 错误：判断条件写反
if (L % T > R % T) {
    // 连续区间（错误！）
}

// ✅ 正确
if (L % T <= R % T) {
    // 连续区间
} else {
    // 分裂
}

易错点 3：边界情况

// 边界：T = 1
if (T == 1) {
    cout << 1;  // 只有一种数对 (0, 0)
    return 0;
}

// 边界：n = 0
if (n == 0) {
    cout << 0;
    return 0;
}

易错点 4：区间合并的索引更新

// ❌ 错误：忘记更新 i
for (int i = 1; i <= tot; i++) {
    while (可以合并) {
        合并...
    }
    // 忘记 i = j，导致重复统计
}

// ✅ 正确
for (int i = 1; i <= tot; i++) {
    int j = i;
    while (可以合并) {
        合并..., j++;
    }
    累加长度;
    i = j;  // 跳过已处理的区间
}

十、子任务分析

子任务 1： $S \le 10^6$

特点：所有区间总长度不超过 $10^6$

策略：

可以直接暴力枚举每个时刻
用 set<pair<ll,ll>> 存储不同的数对
复杂度： $O(S \log S)$

子任务 2： $n = 1$

特点：只有一个区间

简化：

不需要区间合并
直接计算模 $T$ 后的覆盖长度

子任务 4： $B = 1$

特点： $y$ 只能取 $0$

简化：

$y = t \bmod 1 = 0$ （恒为0）
$x = (t + t) \bmod A = 2t \bmod A$
周期 $T = \text{lcm}(A, 2)$
只需统计不同的 $x$ 值个数

子任务 6： $B \le 10^6$

特点：周期相对较小

策略：

$T = \text{lcm}(A, B+1) \le A \cdot B \le 10^{24}$ （但会截断为 $10^{18}$ ）
标准算法可以直接通过

十一、关键数据结构总结

变量	含义	范围
`T`	数对的循环周期	$[1, 10^{18}]$
`A[i].l`	第 $i$ 个归约区间的左端点	$[0, T-1]$
`A[i].r`	第 $i$ 个归约区间的右端点	$[0, T-1]$
`tot`	归约后的区间总数	$[1, 2n]$
`ans`	不同数对的个数	$[1, T]$

十二、算法标签

核心算法

数论 - 最小公倍数、周期分析
区间合并 - 贪心算法
模运算 - 周期归约

辅助技巧

数学推导 - 函数周期性证明
高精度处理 - __int128 防溢出
排序算法 - 区间排序

十三、相关知识点

前置知识

✅ 最大公约数（GCD）
✅ 最小公倍数（LCM）
✅ 模运算性质
✅ 区间合并算法

进阶知识

✅ 周期函数理论
✅ 数论函数的周期性
✅ 中国剩余定理（扩展理解）

ID

3794

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

zhoujinchong2004

1 条题解