2015
09-18

# Just Random

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.

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).

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).

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

Case #1: 1/3
Case #2: 1/1000000
Case #3: 0/1
Case #4: 1/1

第二个区间可以看成：C=[0,1,2,3,4,5]+….D=(0,1）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long

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

ll gcd(ll a, ll b){
if (b == 0)
return a;
return gcd(b,a%b);
}

ll f(ll a, ll b){
if (a < 0 || b < 0)
return 0;
ll ma = a%p, mb = b%p;
ll ans = (a/p)*(b/p)*p;
ans += (ma+1)*(b/p) + (mb+1)*(a/p);
if (ma > m){
ans += min(m, mb) + 1;
ll t = (p+m-ma) % p;
if (t <= mb)
ans +=  mb-t+1;
}
else {
ll t = (p+m-ma)%p;
if (t <= mb)
ans += min(m-t+1, mb-t+1);
}
return ans;
}

int main(){
int cas = 1,t;
scanf("%d", &t);
while (t--){
scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &p, &m);
ll ans = f(b, d)-f(b, c-1)-f(a-1, d)+f(a-1, c-1);
ll tot = (b-a+1)*(d-c+1);
ll g = gcd(ans, tot);
printf("Case #%d: ", cas++);
cout << ans/g << "/" << tot/g << endl;
}
return 0;
}

1. “至于朱德同志的账那就更多了。从井冈山一直打到梅县，都是盲动主义，军阀主义，流寇主义。然后是立三路线，你也犯了。然后是王明路线四年，然后又是洛川会议。那时王明没有回来，那还不是反对毛主席，你没有领导？然后王明回来。第二次王明路线一

2. “至于朱德同志的账那就更多了。从井冈山一直打到梅县，都是盲动主义，军阀主义，流寇主义。然后是立三路线，你也犯了。然后是王明路线四年，然后又是洛川会议。那时王明没有回来，那还不是反对毛主席，你没有领导？然后王明回来。第二次王明路线一

3. “至于朱德同志的账那就更多了。从井冈山一直打到梅县，都是盲动主义，军阀主义，流寇主义。然后是立三路线，你也犯了。然后是王明路线四年，然后又是洛川会议。那时王明没有回来，那还不是反对毛主席，你没有领导？然后王明回来。第二次王明路线一

4. “至于朱德同志的账那就更多了。从井冈山一直打到梅县，都是盲动主义，军阀主义，流寇主义。然后是立三路线，你也犯了。然后是王明路线四年，然后又是洛川会议。那时王明没有回来，那还不是反对毛主席，你没有领导？然后王明回来。第二次王明路线一

5. “至于朱德同志的账那就更多了。从井冈山一直打到梅县，都是盲动主义，军阀主义，流寇主义。然后是立三路线，你也犯了。然后是王明路线四年，然后又是洛川会议。那时王明没有回来，那还不是反对毛主席，你没有领导？然后王明回来。第二次王明路线一

6. “至于朱德同志的账那就更多了。从井冈山一直打到梅县，都是盲动主义，军阀主义，流寇主义。然后是立三路线，你也犯了。然后是王明路线四年，然后又是洛川会议。那时王明没有回来，那还不是反对毛主席，你没有领导？然后王明回来。第二次王明路线一

7. “至于朱德同志的账那就更多了。从井冈山一直打到梅县，都是盲动主义，军阀主义，流寇主义。然后是立三路线，你也犯了。然后是王明路线四年，然后又是洛川会议。那时王明没有回来，那还不是反对毛主席，你没有领导？然后王明回来。第二次王明路线一

8. “至于朱德同志的账那就更多了。从井冈山一直打到梅县，都是盲动主义，军阀主义，流寇主义。然后是立三路线，你也犯了。然后是王明路线四年，然后又是洛川会议。那时王明没有回来，那还不是反对毛主席，你没有领导？然后王明回来。第二次王明路线一

9. “至于朱德同志的账那就更多了。从井冈山一直打到梅县，都是盲动主义，军阀主义，流寇主义。然后是立三路线，你也犯了。然后是王明路线四年，然后又是洛川会议。那时王明没有回来，那还不是反对毛主席，你没有领导？然后王明回来。第二次王明路线一

10. 这才乖咩哈哈哈哈不过两天才来依然算迟到小账本先给你记着体谅你被考试摧残给你打个折吧哈我就说孩子神马的最恐怖了精力无敌旺盛

11. 这才乖咩哈哈哈哈不过两天才来依然算迟到小账本先给你记着体谅你被考试摧残给你打个折吧哈我就说孩子神马的最恐怖了精力无敌旺盛

12. 这才乖咩哈哈哈哈不过两天才来依然算迟到小账本先给你记着体谅你被考试摧残给你打个折吧哈我就说孩子神马的最恐怖了精力无敌旺盛

13. 这才乖咩哈哈哈哈不过两天才来依然算迟到小账本先给你记着体谅你被考试摧残给你打个折吧哈我就说孩子神马的最恐怖了精力无敌旺盛

14. 这才乖咩哈哈哈哈不过两天才来依然算迟到小账本先给你记着体谅你被考试摧残给你打个折吧哈我就说孩子神马的最恐怖了精力无敌旺盛

15. 这才乖咩哈哈哈哈不过两天才来依然算迟到小账本先给你记着体谅你被考试摧残给你打个折吧哈我就说孩子神马的最恐怖了精力无敌旺盛

16. 这才乖咩哈哈哈哈不过两天才来依然算迟到小账本先给你记着体谅你被考试摧残给你打个折吧哈我就说孩子神马的最恐怖了精力无敌旺盛

17. 这才乖咩哈哈哈哈不过两天才来依然算迟到小账本先给你记着体谅你被考试摧残给你打个折吧哈我就说孩子神马的最恐怖了精力无敌旺盛

18. 这才乖咩哈哈哈哈不过两天才来依然算迟到小账本先给你记着体谅你被考试摧残给你打个折吧哈我就说孩子神马的最恐怖了精力无敌旺盛