Codeforces Round #341 (Div. 2) C - Wet Shark and Flowers

C - Wet Shark and Flowers

题目大意：有n个人围成一个圈，每个在l[ i ] 到 r[ i ]之间随机出一个数，如果这个数和旁边的一个人出的数的积是p的倍数，则他得到1000元，如果

和两个人的积都是p (p一定为素数)的倍数，则他得到2000元，让你求所有人得到的钱的期望。

 

思路：我们只需要算出每个人得到钱的期望，然后加在一起就是总的得到的钱的期望，对于一个人和他相邻的人来说，我们只需要知道l[ i ]到r[ i ]里边有

多少个p的倍数就可以求期望啦，具体看代码。

#include<bits/stdc++.h>
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define read(x) scanf("%d",&x)
#define lread(x) scanf("%lld",&x);
using namespace std;
const int N=1e6+5;
int n,mod;
pair<ll,ll> p[N];
double cal(int i,int j)
{
    double ans=0;
    ll len1=p[i].se-p[i].fi+1;
    ll len2=p[j].se-p[j].fi+1;
    ll cnt1=len1-(p[i].se/mod-(p[i].fi-1)/mod);
    ll cnt2=len2-(p[j].se/mod-(p[j].fi-1)/mod);
    ans=1.0-(1.0*cnt1/len1*cnt2/len2);
    return ans*1000;
}
int main()
{
    read(n); read(mod);
    for(int i=0;i<n;i++)
    {
        lread(p[i].fi);
        lread(p[i].se);
    }
    double ans=0;
    for(int i=0;i<n;i++)
    {
        int pre=(i-1+n)%n;
        int nx=(i+1)%n;
        ans+=cal(i,pre);
        ans+=cal(i,nx);
    }
    printf("%.12f\n",ans);
    return 0;
}