链接：

pid=4790">http://acm.hdu.edu.cn/showproblem.php?pid=4790

意：从【a。b】中随机找出一个数字x，从【c。d】中随机找出一个数字y。给出p。m，假设(x+y)%p==m则算成功，问成功的概率是多少。

思路：【a。b】中连续p个数。【c，d】中连续p个数。用这2*p个数进行组合能找到p种的成功组合（详细不证），所以找到【a。b】中p循环的个数x1，【c，d】中p循环的个数y1，则它们组成的成功组合数为p*x1*y1。

然后是处理边界的问题，首先x或y处于边界的数的数量一定不超过p-1个，设分别有x2，y2个，这x2。y2个数一定能在相应的每一个循环中找到相应的成功组合。所以还要多出x2*y1+y2*x1个成功组合数。

最后还要在这x2，y2个数里找到互相相应的数。由于要求x2+y2 ≡ m(mod p)，所以(m-x2) ≡ y2(mod p)，然后找到它们重叠的部分就可以。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <map>

#include <cstdlib>

#include <queue>

#include <stack>

#include <vector>

#include <ctype.h>

#include <algorithm>

#include <string>

#include <set>

#define PI acos(-1.0)

#define maxn 10005

#define INF 0x7fffffff

#define eps 1e-8

typedef long long LL;

typedef unsigned long long ULL;

using namespace std;

int main()

{

    int T;

    scanf("%d",&T);

    for(int ii=1; ii<=T; ii++)

    {

        LL a,b,c,d,p,m;

        scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&p,&m);

        LL x=b-a+1,y=d-c+1;

        LL xx=(b-a+1)/p;

        LL yy=(d-c+1)/p;

        LL xxx=x-xx*p;

        LL yyy=y-yy*p;

        LL t=xx*yy*p;

        LL fm=x*y;

        t+=xxx*yy;

        t+=yyy*xx;

        if(xxx!=0&&yyy!=0)

        {

            LL head=a%p;

            LL tail=b%p;

            LL head1=((m-tail)%p+p)%p;

            LL tail1=((m-head)%p+p)%p;

            LL head2=c%p;

            LL tail2=d%p;

            //cout<<head1<<" "<<tail1<<" "<<head2<<" "<<tail2<<endl;

            if(tail1>=head1&&tail2>=head2)

                t+=(max(0LL,(min(tail2,tail1)-max(head1,head2))+1));

            else if(tail1>=head1&&tail2<head2)

            {

                if(tail1<=tail2)

                    t+=max(0LL,tail1-head1+1);

                else if(tail1>tail2&&tail1<head2)

                    t+=max(0LL,tail2-head1+1);

                else t+=max(0LL,tail1-max(head1,head2)+1)+max(0LL,tail2-head1+1);

            }

            else if(tail2>=head2&&tail1<head1)

            {

                if(tail2<=tail1)

                    t+=max(0LL,tail2-head2+1);

                else if(tail2>tail1&&tail2<head1)

                    t+=max(0LL,tail1-head2+1);

                else t+=max(0LL,tail2-max(head1,head2)+1)+max(0LL,tail1-head2+1);

            }

            else t+=(p-max(head1,head2)+min(tail1,tail2)+1+max(0LL,tail1-head2+1)+max(0LL,tail2-head1+1));

        }

        printf("Case #%d: ",ii);

        if(t==0)

            printf("0/1\n");

        else

        {

            LL ttt=__gcd(t,fm);

            printf("%I64d/%I64d\n",t/ttt,fm/ttt);

        }

    }

    return 0;

}