题目概述

有一条无限长的灯链，灯泡编号从0开始。有n个按钮，每个按钮对应一个互质的正整数 ( p_i ) 和一个颜色 ( k_i )。

Jas 按顺序按下所有按钮，按下第i个按钮时：

• 所有编号能被 ( p_i ) 整除的灯泡都会变成颜色 ( k_i )
• 包括之前已经点亮且能被 ( p_i ) 整除的灯泡也会改变颜色

需要计算每个颜色最终在无限灯泡中所占的比例 ( C_i )。

---

问题分析

关键观察

1. 操作顺序性：后面的操作会覆盖前面的操作
2. 互质条件：所有 ( p_i ) 互质，这简化了问题
3. 最终颜色：一个灯泡的最终颜色由最后一个能整除它的按钮决定

数学建模

设灯泡编号为 ( x )，它的最终颜色由满足 ( p_i \mid x ) 的最大 ( i ) 决定。

由于 ( p_i ) 互质，根据中国剩余定理，每个余数组合对应唯一的解模 ( \prod p_i )。

---

算法思路

核心思想：倒序处理

从最后一个按钮开始向前处理，计算每个按钮"生效"的比例。

对于第i个按钮：

• 它能影响的灯泡是所有能被 ( p_i ) 整除的灯泡
• 但这些灯泡中，有些会被后面的按钮覆盖
• 所以它实际"保留"的灯泡是：能被 ( p_i ) 整除，但不能被任何 ( p_j (j>i) ) 整除的灯泡

比例计算

设 ( S_i ) 表示第i个按钮最终显示的颜色比例，则： [ S_i = \frac{1}{p_i} \times \prod_{j=i+1}^n \left(1 - \frac{1}{p_j}\right) ] 解释：

• ( \frac{1}{p_i} )：能被 ( p_i ) 整除的灯泡比例
• ( \prod (1-\frac{1}{p_j}) )：不被后面任何按钮覆盖的比例

递推计算

从后往前递推：

• 初始化：( A_n = 1, B_n = p_n )
• 对于 ( i ) 从 ( n-1 ) 到 1： [ A_i = A_{i+1} \times (p_i - 1) ] [ B_i = B_{i+1} \times p_i ]
• 然后约分得到最简分数 ( A_i/B_i )

---

算法详解

数据结构

使用高精度数 ppp 来处理大数运算：

struct ppp {
    long long a[4010], clong;  // 存储大数，每块10^9
    void jinwei();  // 进位处理
    void print();   // 输出
};

核心递推

make(A[n], 1);
make(B[n], a[n]);           // 最后一个按钮：比例 = 1/p_n

for (i = n-1; i >= 1; i--) {
    x = a[i] - 1;           // p_i - 1
    y = a[i];               // p_i
    
    // 计算新的分子分母
    A[i] = A[i+1] * x;      // 分子乘(p_i-1)
    B[i] = B[i+1] * y;      // 分母乘p_i
    
    // 约分
    int g = gcd(A[i], B[i]);
    A[i] = A[i] / g;
    B[i] = B[i] / g;
}

特殊情况处理

如果某个 ( p_i = 1 )，那么它会影响所有灯泡，前面的按钮都不会显示：

if (x == 0) {  // 即 p_i = 1
    D = i - 1; // 前面所有按钮比例都为0
    break;
}

---

样例解析

样例输入

3
2
3
5

计算过程

从后往前：

1. 按钮3 (p=5)：

   • 比例 = 1/5

2. 按钮2 (p=3)：

   • 比例 = (1/5) × (3-1)/3 = (1/5) × (2/3) = 2/15
   • 但注意：按钮2的实际比例应该是 1/3 × (1-1/5) = 1/3 × 4/5 = 4/15

3. 按钮1 (p=2)：

   • 比例 = (4/15) × (2-1)/2 = (4/15) × 1/2 = 4/30 = 2/15
   • 但实际应该是 1/2 × (1-1/3) × (1-1/5) = 1/2 × 2/3 × 4/5 = 8/30 = 4/15

输出：

4/15  (按钮1)
4/15  (按钮2)  
1/5   (按钮3)

正确公式

第i个按钮的最终比例： [ C_i = \frac{1}{p_i} \times \prod_{j=i+1}^n \left(1 - \frac{1}{p_j}\right) ]

---

复杂度分析

• 时间复杂度：( O(n \times \text{高精度操作时间}) )
  • 每个按钮进行常数次高精度运算
• 空间复杂度：( O(n \times \text{高精度存储}) )
  • 存储所有分数的分子分母

---

算法亮点

1. 倒序处理：利用操作顺序性，从后往前计算
2. 高精度运算：处理大数乘积和约分
3. 互质性质：简化独立事件概率计算
4. 公式推导：通过概率论得出简洁表达式

---

总结

这道题的核心在于理解操作覆盖的顺序效应：

1. 问题转化：将灯泡着色问题转化为概率计算
2. 独立事件：利用互质条件，各按钮影响独立
3. 递推计算：从后往前计算每个按钮的"净影响"
4. 高精度处理：应对大数运算需求

这种"倒序处理 + 概率计算"的方法在解决有覆盖关系的操作序列问题时非常有效。