Description
在区间a,b 和 c,d 中等概率选择一个数 问两个数异或和为0的概率是多少
Solution
异或和为0 就是两个数相等 那就是在a,b c,d区间中分别选一个数 问两个数相等概率是多少 很显然就是求交集 先求总长度 然后再求交集长度 化简成最简形式就好了
Code
#include <bits/stdc++.h> using namespace std; #define LL long long #define ULL unsigned long long #define mes(x, a) memset(x, a, sizeof(x)); #define sca(a) scanf("%d", &a) #define lowbit(x) x &(-x) #define mk make_pair #define pb(x) push_back(x) #define all(x) (x).begin(), (x).end() #define fi first #define se second #define lson v << 1 #define rson v << 1 | 1 #define pii pair<int, int> inline void read(int &x) { x = 0; int flag_read = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') flag_read = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + c - '0'; c = getchar(); } x *= flag_read; } void out(int x) { if (x > 9) { out(x / 10); } putchar(x % 10 + '0'); } int main() { LL a, b, c, d; while (cin >> a >> b >> c >> d) { if(a > d || b < c){//不相交 左端点大于另一条右端点 右端点小于另一条左端点 cout << "0/1" << '\n'; continue; } LL sum = (b - a + 1) * (d - c + 1) ;///所有选择 LL l = min(b, d) - max(a, c) + 1;//相交长度 LL z = __gcd(l,sum); cout << l / z << '/' << sum / z<< '\n'; } return 0; }