HDU4790-白红宇

HDU4790

阅读量：5158 次

发布时间：2019-06-13

本文共 2841 字，大约阅读时间需要 9 分钟。

题意：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 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
               10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 #include 
                   
                     15 using namespace std; 16 #define PI acos( -1.0 ) 17 typedef long long ll; 18 typedef pair
                    
                      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\n", 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 }