异或时间限制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 ≤ bc ≤ da≤bc≤d1 ≤ 数据组数 ≤ 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分数化简。效率保障纯数学计算无循环极速处理大数据与多组输入无精度误差。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll a,b,c,d;voidsolve(){ll lmax(a,c),rmin(b,d);ll cntmax(0LL,r-l1);ll mul(b-a1)*(d-c1);if(cnt0)cout0/1endl;else{ll ggcd(cnt,mul);coutcnt/g/mul/gendl;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);while(cinabcd)solve();return0;}