hdu 4790 Just Random (思路+分类计算+数学)

Problem Description

Coach Pang and Uncle Yang both love numbers. Every morning they play a game with number together. In each game the following will be done:

　　. Coach Pang randomly choose a integer x in [a, b] with equal probability.

　　. Uncle Yang randomly choose a integer y in [c, d] with equal probability.

　　. If (x + y) mod p = m, they will go out and have a nice day together.

　　. Otherwise, they will do homework that day.

　　For given a, b, c, d, p and m, Coach Pang wants to know the probability that they will go out.

Input

The first line of the input contains an integer T denoting the number of test cases.

　　For each test case, there is one line containing six integers a, b, c, d, p and m( <= a <= b <= ,  <=c <= d <= ,  <= m < p <= ).

Output

For each test case output a single line "Case #x: y". x is the case number and y is a fraction with numerator and denominator separated by a slash ('/') as the probability that they will go out. The fraction should be presented in the simplest form (with the smallest denominator), but always with a denominator (even if it is the unit).

Sample Input

Sample Output

Case #: / 
Case #: / 
Case #: / 
Case #: /

Source

2013 Asia Chengdu Regional Contest

思路：对于a<=x<=b,c<=y<=d，满足条件的结果为ans=f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1)。

而函数f(a,b)是计算0<=x<=a,0<=y<=b满足条件的结果。这样计算就很方便了。

例如：求f(16,7),p=6,m=2.

对于x有：0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4

对于y有：0 1 2 3 4 5 0 1

很容易知道对于xy中的（0 1 2 3 4 5）对满足条件的数目为p。

这样取A集合为（0 1 2 3 4 5 0 1 2 3 4 5），B集合为（0 1 2 3 4）。

C集合为（0 1 2 3 4 5），D集合为（0 1）。

这样就可以分成4部分来计算了。

f(16,7)=A和C满足条件的数+A和D满足条件的数+B和C满足条件的数+B和D满足条件的数。

其中前3个很好求的，关键是B和D满足条件的怎么求！

这个要根据m来分情况。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define ll long long

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

 ll gcd(ll x,ll y)

 {

     return y==?x:gcd(y,x%y);

 }

 ll f(ll x,ll y)

 {

     if(x< || y<)

          return ;

     ll mx=x%p;

     ll my=y%p;

     ll ans=;

     ans=ans+(x/p)*(y/p)*p;//

     ans=ans+(x/p)*(my+); //

     ans=ans+(y/p)*(mx+);//

     if(mx>m)//

     {

         ans=ans+min(my,m)+;

         ll t=(p+m-mx);

         if(t<=my)

             ans=ans+my-t+;

     }

     else//

     {

         ll t=(p+m-mx)%p;

         if(t<=my) ans=ans+min(my-t+,m-t+);

     }

     return ans;

 }

 int main()

 {

     int t;

     int ac=;

     scanf("%d",&t);

     while(t--)

     {

         printf("Case #%d: ",++ac);

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

         ll ans=f(b,d)-f(b,c-)-f(a-,d)+f(a-,c-);

         ll tot=(b-a+)*(d-c+);

         ll r=gcd(ans,tot);

         printf("%I64d/%I64d\n",ans/r,tot/r);

     }

     return ;

 }

Recommend

巴特西

hdu 4790 Just Random (思路+分类计算+数学)

最新文章

热门文章