有 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$$。
在第二个样本中,任何数量的组合都不会给鲨鱼带来任何金钱。