CF621C Wet Shark and Flowers

Wet Shark 有 $n$ 只种花的鲨鱼，它们都围坐在一张桌子旁。对于所有 $1 \leq i \leq n-1$，鲨鱼 $i$ 和鲨鱼 $i+1$ 是邻居。鲨鱼 $n$ 与鲨鱼 $1$ 也是邻居。 每只鲨鱼会种若干朵花，设为 $s_i$。对于第 $i$ 只鲨鱼，$s_i$ 是从 $l_i$ 到 $r_i$（含）之间均匀随机选取的一个整数。Wet Shark 有一个最喜欢的质数 $p$，它对这个质数非常喜爱！对于任意一对相邻的鲨鱼 $i$ 和 $j$，如果 $s_i \cdot s_j$ 能被 $p$ 整除，Wet Shark 就会对这两只鲨鱼各奖 $1000$ 美元。 一天结束后，所有鲨鱼会把 Wet Shark 奖励它们的奖金加起来。请你求出这些奖金的期望值。

输入的第一行包含两个用空格隔开的整数 $n$ 和 $p$（$3 \leq n \leq 100000, 2 \leq p \leq 10^9$）——鲨鱼的数量和 Wet Shark 喜欢的质数。保证 $p$ 是一个质数。 接下来的 $n$ 行，第 $i$ 行包含两个用空格隔开的整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 10^9$），表示第 $i$ 只鲨鱼能种植的花的范围。注意，$s_i$ 在 $[l_i, r_i]$ 区间内等概率取整数值。

输出一个实数，表示所有鲨鱼最终获得奖金的期望总和。只要你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。 具体来说，设你的答案为 $a$，标准答案为 $b$，如果 $\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$，则为正确。

质数是指仅能被 $1$ 和它自身整除的正整数。$1$ 不被视为质数。 考虑第一个样例。第一只鲨鱼能种植 $1$ 至 $2$ 朵花，第二只鲨鱼能种植 $420$ 至 $421$ 朵花，第三只鲨鱼能种植 $420420$ 至 $420421$ 朵花。三只鲨鱼能种植的花的数量共有 $8$ 种组合 $(s_0, s_1, s_2)$： 1. $(1,420,420420)$：注意 $s_0 \cdot s_1 = 420$，$s_1 \cdot s_2 = 176576400$，$s_2 \cdot s_0 = 420420$。每对相邻鲨鱼都能获得 $1000$ 美元，因此每只鲨鱼获得 $2000$ 美元，总奖金 $6000$。 2. $(1,420,420421)$：此时 $s_2 \cdot s_0$ 不能被 $2$ 整除，只有 $s_0, s_1$ 和 $s_1, s_2$ 这两对邻居各得 $1000$ 美元，即总奖金 $4000$。 3. $(1,421,420420)$：总奖金 $4000$。 4. $(1,421,420421)$：总奖金 $0$。 5. $(2,420,420420)$：总奖金 $6000$。 6. $(2,420,420421)$：总奖金 $6000$。 7. $(2,421,420420)$：总奖金 $6000$。 8. $(2,421,420421)$：总奖金 $4000$。 期望奖金为 $\frac{1}{8} (6000+4000+4000+0+6000+6000+6000+4000) = 4500$。 第二个样例中，任何花的组合都不能获得奖金。 由 ChatGPT 5 翻译