HDU4790

题意：x 属于[a, b] , y 属于[c, d], 求（ x+y ）% p = m 的概率。

思路：模拟 a+b, a+b+1 ...... ...... a+d-1, a+d

　　　　　　　　a+1+b ...... ...... a+d-1, a+d, a+d+1

　　　　　　　　　　a+2+b ...... ...... ... a+d, a+d+1, a+d+2

　　　　　　　　　　　　......

　　　　　　　　　　　　　　b+c, b+1+c ...... ...... b+d-1, b+d

　　讨论（b+c）与（a+d）的大小分成俩中情况

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <cctype>
  6 #include <time.h>
  7 #include <string>
  8 #include <set>
  9 #include <map>
 10 #include <queue>
 11 #include <vector>
 12 #include <stack>
 13 #include <algorithm>
 14 #include <iostream>
 15 using namespace std;
 16 #define PI acos( -1.0 )
 17 typedef long long ll;
 18 typedef pair<int,int> P;
 19 const double E = 1e-8;
 20 
 21 ll a, b, c, d, p, m;
 22 
 23 ll gcd( ll x, ll y )
 24 {
 25     if( y == 0 )
 26         return x;
 27     return gcd( y, x%y );
 28 }
 29 
 30 void Solve()
 31 {
 32     ll ans = 0;
 33     if( a+d >= b+c )
 34     {
 35         ll ys1 = ( a + c ) % p;
 36         ll x1 = ( m - ys1 + p ) % p;
 37         ll num1 = ( x1 + a + c - m ) / p;
 38         ll ys2 = ( b + c - 1 ) % p;
 39         ll x2 = ( ys2 - m + p ) % p;
 40         ll num2 = ( b + c - 1 - x2 - m ) / p;
 41         ans += ( num2-num1 + 1 )*( x1+1 ) + ( num2-num1 + 1 )*( num2-num1 ) / 2 * p;
 42 
 43         ys1 = ( b + c ) % p;
 44         x1 = ( m- ys1 + p ) % p;
 45         num1 = ( x1 + b + c - m ) / p;
 46         ys2 = ( a + d ) % p;
 47         x2 = ( ys2 - m + p ) % p;
 48         num2 = ( a + d - x2 - m ) / p;
 49         ans += ( num2 - num1 + 1 )*( b - a + 1 );
 50 
 51         ys1 = ( a + d + 1 ) % p;
 52         x1 = ( m - ys1 + p ) % p;
 53         num1 = ( x1 + 1 + a + d - m ) / p;
 54         ys2 = ( b + d ) % p;
 55         x2 = ( ys2 - m + p ) % p;
 56         num2 = ( b + d - x2 - m ) / p;
 57         ans += ( num2-num1+1 )*( x2+1 ) + ( num2-num1+1 )*( num2-num1 ) / 2 * p;
 58     }
 59     else
 60     {
 61         ll ys1 = ( a + c ) % p;
 62         ll x1 = ( m - ys1 + p ) % p;
 63         ll num1 = ( a + c + x1 - m ) / p;
 64         ll ys2 = ( a + d - 1 ) % p;
 65         ll x2 = ( ys2 - m + p ) % p;
 66         ll num2 = ( a + d - 1 - x2 - m ) / p;
 67         ans += ( num2-num1+1 )*( x1+1 ) + ( num2-num1+1 )*( num2-num1 ) / 2 * p;
 68 
 69         ys1 = ( a + d ) % p;
 70         x1 = ( m - ys1 + p ) % p;
 71         num1 = ( a + d + x1 - m ) / p;
 72         ys2 = ( b + c ) % p;
 73         x2 = ( ys2 - m + p ) % p;
 74         num2 = ( b + c - x2 - m ) / p;
 75         ans += ( num2-num1+1 )*( d - c + 1 );
 76 
 77         ys1 = ( b + c + 1 ) % p;
 78         x1 = ( m - ys1 + p ) % p;
 79         num1 = ( b + c + 1 + x1 - m ) / p;
 80         ys2 = ( b + d ) % p;
 81         x2 = ( ys2 - m + p ) % p;
 82         num2 = ( b + d - x2 - m ) / p;
 83         ans += ( num2-num1+1 )*( x2+1 ) + ( num2-num1+1 )*( num2-num1 ) / 2 * p;
 84     }
 85     ll num = ( b-a+1 )*( d-c+1 );
 86     ll mod = gcd( num, ans );
 87     printf( "%I64d/%I64d
", ans/mod, num/mod );
 88 }
 89 
 90 int main()
 91 {
 92     int T, tcase = 0;
 93     scanf( "%d", &T );
 94     while( T-- )
 95     {
 96         scanf( "%I64d%I64d%I64d%I64d%I64d%I64d", &a, &b, &c, &d, &p, &m );
 97         printf( "Case #%d: ", ++tcase );
 98         Solve();
 99     }
100     return 0;
101 }

View Code