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: 1. Coach Pang randomly choose a integer x in [a, b] with equal probability. 2. Uncle Yang randomly choose a integer y in [c, d] with equal probability. 3. If (x + y) mod p = m, they will go out and have a nice day together. 4. 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(0 <= a <= b <= 109, 0 <=c <= d <= 109, 0 <= m < p <= 109).
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
4
0 5 0 5 3 0
0 999999 0 999999 1000000 0
0 3 0 3 8 7
3 3 4 4 7 0
Sample Output
Case #1: 1/3
Case #2: 1/1000000
Case #3: 0/1
Case #4: 1/1
Source
思路：对于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来分情况。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 #define ll long long 6 ll a,b,c,d,p,m; 7 ll gcd(ll x,ll y) 8 { 9 return y==0?x:gcd(y,x%y); 10 } 11 ll f(ll x,ll y) 12 { 13 if(x<0 || y<0) 14 return 0; 15 ll mx=x%p; 16 ll my=y%p; 17 ll ans=0; 18 ans=ans+(x/p)*(y/p)*p;//1 19 ans=ans+(x/p)*(my+1); //2 20 ans=ans+(y/p)*(mx+1);//3 21 22 if(mx>m)//4 23 { 24 ans=ans+min(my,m)+1; 25 ll t=(p+m-mx); 26 if(t<=my) 27 ans=ans+my-t+1; 28 } 29 else//4 30 { 31 ll t=(p+m-mx)%p; 32 if(t<=my) ans=ans+min(my-t+1,m-t+1); 33 } 34 return ans; 35 } 36 int main() 37 { 38 int t; 39 int ac=0; 40 scanf("%d",&t); 41 while(t--) 42 { 43 printf("Case #%d: ",++ac); 44 scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&p,&m); 45 ll ans=f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1); 46 ll tot=(b-a+1)*(d-c+1); 47 ll r=gcd(ans,tot); 48 printf("%I64d/%I64d ",ans/r,tot/r); 49 } 50 return 0; 51 }
Recommend