http://www.cnblogs.com/xin-hua/p/3553045.html
思路:对于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部分来计算了。
Just Random
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1151 Accepted Submission(s): 315
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.
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).
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).
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
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long int LL; LL a,b,c,d,p,m; LL getF(LL x,LL y) { x++,y++; LL nn=x/p,mm=y/p; LL rn=x%p,rm=y%p; LL res1=nn*mm*p; LL res2=nn*rm; LL res3=mm*rn; LL res4=0; if(rn<=rm) { LL l1=rn; LL l2=rm; for(LL i=m+1;i<rn+rm;i+=p) { if(i<l1) res4+=i; else if(i>=l1&&i<=l2) res4+=rn; else res4+=rn+rm-i; } } else { LL l1=rm; LL l2=rn; for(LL i=m+1;i<rn+rm;i+=p) { if(i<l1) res4+=i; else if(i>=l1&&i<=l2) res4+=rm; else res4+=rn+rm-i; } } return res1+res2+res3+res4; } LL gcd(LL a,LL b) { if(b==0) return a; return gcd(b,a%b); } int main() { int T_T,cas=1; scanf("%d",&T_T); while(T_T--) { cin>>a>>b>>c>>d>>p>>m; LL A=(b-a+1)*(d-c+1); LL B=getF(b,d)-getF(a-1,d)-getF(b,c-1)+getF(a-1,c-1); LL G=gcd(A,B); cout<<"Case #"<<cas++<<": "<<B/G<<"/"<<A/G<<endl; } return 0; }