← 返回题目列表

Codeforces · 621/C

C. 湿鲨鱼和花

中文机器翻译题面 查看原题

有 n 只鲨鱼为湿鲨鱼种花。它们都坐在桌子周围,这样鲨鱼 i 和 i + 1 是从 1 到 n - 1 的所有 i 的邻居。鲨鱼 n 和 1 也是邻居。

每只鲨鱼都会长出一定数量的花si。对于第 i 个鲨鱼值 si 是在 li 到 ri 范围内等概率选择的随机整数。湿鲨鱼有它最喜欢的素数 p,他真的很喜欢它!如果对于任何一对相邻的鲨鱼 i 和 j,其乘积 si·sj 可以被 p 整除,那么 Wet Shark 就会很高兴,并给每条鲨鱼 1000 美元。

一天结束时,鲨鱼会将 Wet Shark 授予它们的所有资金相加。求该值的期望值。

输入

输入的第一行包含两个空格分隔的整数 n 和 p (3 ≤ n ≤ 100 000, 2 ≤ p ≤ 109) - 鲨鱼的数量和 Wet Shark 最喜欢的素数。保证p是素数。

以下 n 行中的第 i 行包含有关第 i 个鲨鱼的信息 — 两个空格分隔的整数 li 和 ri (1 ≤ li ≤ ri ≤ 109),即花鲨 i 可以产生的范围。请记住,si 是在从 li 到 ri(含)的所有整数中等概率选择的。

输出

打印一个实数——鲨鱼总共收到的美元的预期数量。如果绝对或相对误差不超过 10 - 6,您的答案将被视为正确。

即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

3 2
1 2
420 421
420420 420421

输出 #1

4500.0

输入 #2

3 5
1 4
2 3
11 14

输出 #2

0.0

注意

素数是只能被 1 和它本身整除的正整数。 1 不被视为素数。

考虑第一个样本。第一个鲨鱼长出了 1 到 2 朵花,第二个鲨鱼长出了 420 到 421 朵花,第三个鲨鱼长出了 420420 到 420421 朵花。每只鲨鱼长出的花数量 (s0, s1, s2) 有八种情况:

1. (1, 420, 420420):注意s0·s1 = 420,s1·s2 = 176576400,s2·s0 = 420420。每对鲨鱼每条奖励1000美元。因此,每条鲨鱼将获得2000美元奖励,总计6000美元。
2. (1, 420, 420421):现在,乘积 s2·s0 不能被 2 整除。因此,鲨鱼 s0 和 s2 将获得 1000 美元,而鲨鱼 s1 将获得 2000 美元。总计为 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 { 6 0 0 0 + 4 0 0 0 + 4 0 0 0 + 0 + 6 0 0 0 + 6 0 0 0 + 6 0 0 0 + 4 0 0 0 } { 8 } } = 4 5 0 0$$。

在第二个样本中,任何数量的组合都不会给鲨鱼带来任何金钱。