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的点的个数 ，然后用个数比上没有条件的（x+y）总的个数
题解：对于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满足条件的结果，画个图就知道了
0 a b
c a+c
d b+d
就是这个图，想象成有4个表格，我们求得就是右下角那个表格的数目~~~
打表代码，打了半天有规律，然后杠了5小时没写出来，又换了个方法，打表代码没啥用，不过我还是放上吧，用这个打表可以做出来，我没写出来而已~~~
打表代码：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,b,c,d,p,m;
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&p,&m);
int k=1;
ll x=0;
int w=2;
for (ll i = a; i <= b;i++){
for (ll j = c; j <= d;j++){
if((i+j)%p==m) x++;
cout << ((i+j)%p==m? 1:0) << " ";
}
cout << endl;
for (int i = 1; i <= w;i++){
cout << " ";
}
w+=2;
}
printf("Case #%d: ",k++);
ll zz=(b-a+1)*(d-c+1);
cout << x << " " << zz << endl;
ll xx=__gcd(x,zz);
if(x==0){
cout << "0/1" << endl;
}
else {
if(xx==0){
cout << x << "/" << zz << endl;
}
else cout << x/xx << "/" << zz/xx << endl;
}
}
return 0;
} 另一种思路：
例如：求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
很容易知道对于x，y中的（0 1 2 3 4 5）对满足条件的数目为p。
这个也是画个图就知道了：
0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
5 6 7 8 9 10
%p后
0 1 2 3 4 5
1 2 3 4 5 0
2 3 4 5 0 1
3 4 5 0 1 2
4 5 0 1 2 3
5 0 1 2 3 4
这样取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 <algorithm>
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 ma=a%p,mb=b%p,ans;
ans=(a/p)*(b/p)*p;//1
ans+=(ma+1)*(b/p)+(mb+1)*(a/p);//2+3 加一是因为还有0，仔细想一下
if(ma>m){ //4
ans+=min(m,mb)+1;//需要自行画图看
ll t=(p+m-ma)%p;//根据ma求出满足最小的y来
if(t<=mb) ans+=mb-t+1;
}
else{
ll t=(p+m-ma)%p;//根据ma求出满足最小的y来
if(t<=mb) ans+=min(m-t+1,mb-t+1);//需要自行画图看
}
return ans;
}
int main(){
int cas=1;
int t;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&p,&m);
ll x=f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1);
printf("Case #%d: ",cas++);
ll zz=(b-a+1)*(d-c+1);
ll xx=__gcd(x,zz);
if(x==0) cout << "0/1" << endl;
else {
if(xx==0) cout << x << "/" << zz << endl;
else cout << x/xx << "/" << zz/xx << endl;
}
}
return 0;
}
京公网安备 11010502036488号