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;
}