Just Random（思维+数学找规律+容斥）

题目链接：https://cn.vjudge.net/problem/HDU-4790

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 <= 10 9, 0 <=c <= d <= 10 9, 0 <= m < p <= 10 9).

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

题意：这个题的意思是给你一个区域[a, b] [c, d]让你求出这个区域中(x+y)%p = m的点的个数，然后用个数比上（b-a+1）*（d-c+1）

题解：对于a<=x<=b,c<=y<=d，满足条件的结果为ans=f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1)，函数f的意思是求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

这样取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满足条件的怎么求！

把所有情况列出来，发现是个平行四边形，每个数出现的次数是有规律的，所以就能做了

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,c,d,p,m;
ll f(ll a,ll b){
	if(a<0||b<0) return 0;
	ll ans=0;
	a++,b++;
    ans+=p*(a/p)*(b/p);
    ans+=(a%p)*(b/p);
    ans+=(b%p)*(a/p);
    ll l1=a%p-1,l2=b%p-1;
    if(l1>l2) swap(l1,l2);
    for(ll i=m;i<=l1+l2;i+=p){
    	if(i<l1) ans+=(i+1);
    	else if(i>=l1&&i<=l2) ans+=(l1+1);
    	else if(i>l2) ans+=(l1+l2-i+1);
	}
	return ans;
}
void solve(){
	ll up=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1);
	ll down=(b-a+1)*(d-c+1);
	cout<<up<<endl;
	ll k=__gcd(up,down);
	up/=k;
	down/=k;
	printf("%lld/%lld\n",up,down);	
}
int main(){
	int T;
	scanf("%d",&T);
	for(int k=1;k<=T;k++){
		scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&p,&m);
		printf("Case #%d: ",k);
		solve();
	}
	return 0;
}