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:
- Coach Pang randomly choose a integer x in [a, b] with equal probability.
- Uncle Yang randomly choose a integer y in [c, d] with equal probability.
- 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<=x<=b c<=y<=d 求满足 (x+y) % p ==m 的概率
这题需要找规律 然后根据规律求解
每一个数出现的次数为 上升的等差数列 相同的值 下降的等差数列
以下看规律
- 0 5 0 5 3 0
- 0 1 1 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 7 7 7 7 8 8 8 9 9 10
- 3 7 2 5 4 6
- 5 6 6 7 7 7 8 8 8 8 9 9 9 9 10 10 10 11 11 12
- 1 3 2 6 2 5
- 3 4 4 5 5 5 6 6 6 7 7 7 8 8 9
然后根据等差数列求和 求解
- #include <cstdio>
- #include <cstring>
- #include <queue>
- #include <cmath>
- #include <algorithm>
- #include <set>
- #include <iostream>
- #include <map>
- #include <stack>
- #include <string>
- #include <vector>
- #define pi acos(-1.0)
- #define eps 1e-6
- #define fi first
- #define se second
- #define lson l,m,rt<<1
- #define rson m+1,r,rt<<1|1
- #define rtl rt<<1
- #define rtr rt<<1|1
- #define bug printf("******\n")
- #define mem(a,b) memset(a,b,sizeof(a))
- #define name2str(x) #x
- #define fuck(x) cout<<#x"="<<x<<endl
- #define f(a) a*a
- #define sf(n) scanf("%d", &n)
- #define sff(a,b) scanf("%d %d", &a, &b)
- #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
- #define sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
- #define pf printf
- #define FRE(i,a,b) for(i = a; i <= b; i++)
- #define FREE(i,a,b) for(i = a; i>= b; i--)
- #define FRL(i,a,b) for(i = a; i <b; i++)
- #define FRLL(i,a,b) for(i = a; i> b; i--)
- #define FIN freopen("in.txt","r",stdin)
- #define gcd(a,b) __gcd(a,b)
- #define lowbit(x) x&-x
- using namespace std;
- typedef long long LL;
- typedef unsigned long long ULL;
- const int mod = 1e9 + 7;
- const int maxn = 1e5 + 10;
- const int INF = 0x3f3f3f3f;
- const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
- int _;
- LL a, b, c, d, m, p;
- LL solveL ( LL L, LL R ) {
- LL cnt = L % p;
- if ( cnt> m ) cnt = L + p - cnt + m;
- else cnt = L + m - cnt ;
- if ( cnt> R ) return 0;
- else {
- int temp = cnt - ( a + c ) + 1;
- int num = ( R - cnt ) / p + 1;
- LL sum = 1LL * temp * num + 1LL * num * ( num - 1 ) * p / 2;
- return sum;
- }
- }
- LL solveM ( LL L, LL R ) {
- LL cnt = L % p;
- if ( cnt> m ) cnt = L + p - cnt + m;
- else cnt = L + m - cnt ;
- if ( cnt> R ) return 0 ;
- else {
- LL temp = L - ( a + c ) + 1;
- LL num = ( R - cnt ) / p + 1;
- LL sum = 1LL * temp * num;
- return sum;
- }
- }
- LL solveR ( LL L, LL R ) {
- LL cnt = L % p;
- if ( cnt> m ) cnt = L + p - cnt + m;
- else cnt = L + m - cnt ;
- if ( cnt> R ) return 0 ;
- else {
- LL temp = ( b + d ) - cnt + 1;
- LL num = ( R - cnt ) / p + 1;
- LL sum = 1LL * temp * num - 1LL * num * ( num - 1 ) * p / 2;
- return sum;
- }
- }
- int main() {
- sf ( _ );
- int cas = 1;
- while ( _-- ) {
- scanf ( "%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &p, &m );
- LL L = a + c, R = b + d, l = min ( b + c, a + d ), r = max ( b + c, a + d ), ans = 0;
- ans += solveL ( L, l - 1 );
- ans += solveM ( l, r );
- ans += solveR ( r + 1, R );
- LL sum = ( b - a + 1 ) * ( d - c + 1 );
- LL g = gcd ( ans, sum );
- printf ( "Case #%d: %lld/%lld\n", cas++, ans / g, sum / g );
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2781846.html