异或
时间限制：1秒 空间限制：32M
知识点：gcd与exgcd
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
C w b c CwbcCwbc想测试一下他的加密协议，以便防止其他人偷看他给X H R l y b XHRlybXHRlyb的信。
C w b c CwbcCwbc提出了这样一个问题：在区间[ a , b ] [a,b][a,b]和区间[ c , d ] [c,d][c,d]中分别等概率随机选择一个整数，两者异或之后等于0 00的概率是多少？
X H R l y b XHRlybXHRlyb一眼就看出了这个题目的答案，但她想让你计算一下这个概率。为了防止精度误差，你只需要输出一个形如a / b a/ba/b的最简分数。特别的，如果概率为0 00，你需要输出0 / 1 0/10/1。
聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！
输入描述：
输入数据有多行，每行有四个非负整数a , b , c , d a, b, c, da,b,c,d。
输出描述：
输出数据应有多行，每行有一个表示答案，形如x / y x/yx/y的最简分数。
示例1
输入：
1 2 3 4输出：
0/1示例2
输入：
1 2 2 3输出：
1/4备注：
a , b , c , d ∈ [ 0 , 10 9 ] a, b, c, d∈[0, 10^9]a,b,c,d∈[0,109]。
a ≤ b ， c ≤ d a ≤ b，c ≤ da≤b，c≤d
1 ≤ 数据组数 ≤ 1000 1 ≤ 数据组数 ≤ 10001≤数据组数≤1000。
解题思路
本题核心是异或性质转化 + 区间交集计算 + 分数最简化简，快速求解概率问题。根据异或运算规则，两数异或结果为0的充要条件是两数相等，因此问题简化为：统计两个区间内相等整数的数量，除以总选取情况数得到概率。首先计算区间[ a , b ] [a,b][a,b]与[ c , d ] [c,d][c,d]的交集长度（有效相等数个数），总情况数为两个区间长度的乘积。利用最大公约数（gcd）将分数化为最简形式，若交集为空则概率为0，输出0/1，否则输出化简后的分数。算法为常数级运算O ( 1 ) O(1)O(1)，完美适配10 9 10^9109级数值与多组测试用例。
总结
核心逻辑：异或为0等价于两数相等，将概率问题转化为区间交集统计。
关键操作：计算区间交集长度、统计总情况数、gcd分数化简。
效率保障：纯数学计算无循环，极速处理大数据与多组输入，无精度误差。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll a,b,c,d;voidsolve(){ll l=max(a,c),r=min(b,d);ll cnt=max(0LL,r-l+1);ll mul=(b-a+1)*(d-c+1);if(cnt==0)cout<<"0/1"<<endl;else{ll g=gcd(cnt,mul);cout<<cnt/g<<"/"<<mul/g<<endl;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);while(cin>>a>>b>>c>>d)solve();return0;}
