2598: 星露谷物语
[Creator : ]
Description
在《星露谷物语》中，Lewis是鹈鹕镇的镇长，号称鹈鹕镇现金王，因为不管你卖多少东西他总会有钱给你。。
今天是秋季的星露谷展览会，有 n 个农民带来了他们自己种的农作物，他们都围坐在桌子旁，这样一来农民 i 和 i+1 就是相邻的，农民 1 和 n 也是相邻的。
每个农民带来的农作物的价值为 s ,第 i 个农民的农作物价值 si 是在 li 到 ri 之间随机选择的整数(每个整数被选择的概率是相同的)，Lewis有他最喜欢的素数 p，如果对于任何一对相邻的农民 i和 j ，有乘积 si × sj 可以被 p 整除，那么Lewis就会很高兴，并给这一对农民每人1000元。
当展览会结束时，所有农民会将他们得到的钱全部加起来，求这个值的期望值。
Input
输入的第一行包含两个空格分隔的整数 n 和 p ( 3 ≤ n ≤ 105 , 2 ≤ p ≤ 109)--农民的数量和Lewis最喜欢的素数。数据保证 p 为素数。
接下来 n 行中的第 i 行包含两个整数 li 和 ri ( 1 ≤ li ≤ ri ≤ 109 ),即第 i 个农民的农作物的价值范围。(请记住, li 和 ri 之间包含这两个数在内的所有整数被选择的概率是相同的)
Output
输出一个实数--所有农民预期收到的钱的总数。答案保留两位小数。
Sample Input Copy
3 2
1 2
420 421
420420 420421
Sample Output Copy
4500.00
HINT
请看样例:
第一个农民的农作物价值范围从 1 到 2 ，第二个农民的农作物价值从 420 到 421 ，第三个农民的农作物价值从 420420 到 420421 。每个农民的农作物价值 (s0, s1, s2) 的数量有八种情况：
- (1, 420, 420420) ：注意 s0·s1 = 420 、 s1·s2 = 176576400 和 s2·s0 = 420420 。每对农民将获得 1000 元,共6000。
- (1, 420, 420421) ：现在，积 s2·s0 不能被 2 整除。因此，农民 s0 和 s2 将获得 1000 元，而农民 s1 将获得 2000 元。总数为 4000。
- (1, 421, 420420) ：总数为 4000。
- (1, 421, 420421) ：总数为 0。
- (2, 420, 420420) ：总数是 6000。
- (2, 420, 420421) ：总数是 6000。
- (2, 421, 420420) ：总数是 6000。
- (2, 421, 420421) ：总数为 4000。