异或故事时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定t tt组询问76 7676每次询问都会给出一个正整数a aa你需要在区间[ 1 , 10 9 ] [1, 10^9][1,109]中找到两个正整数b bb和c cc使得b ⊕ c a b \oplus c ab⊕ca。⊕ 代表按位异或。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≤ T ≤ 10 5 ) T\ (1 \le T \le 10^5)T(1≤T≤105)代表数据组数每组测试数据描述如下在一行上输入一个整数a ( 1 ≤ a ≤ 10 9 ) a\ (1 \le a \le 10^9)a(1≤a≤109)代表76 7676给出的初始数字。输出描述对于每一组测试数据在一行上输出两个正整数代表你找到的两个值。如果存在多个解决方案您可以输出任意一个。示例 1输入3 1 5 4输出2 3 3 6 74 78说明对于第一组测试数据( 10 ) 2 xor ( 11 ) 2 ( 01 ) 2 (10)_2 \mathbin{\text{xor}} (11)_2 (01)_2(10)2xor(11)2(01)2对于第二组测试数据( 011 ) 2 xor ( 110 ) 2 ( 101 ) 2 (011)_2 \mathbin{\text{xor}} (110)_2 (101)_2(011)2xor(110)2(101)2。解题思路本题是位运算构造问题。给定正整数a aa需要在[ 1 , 10 9 ] [1,10^9][1,109]内找出两个正整数b , c b,cb,c使得b ⊕ c a b \oplus c ab⊕ca。利用二进制中最低位1 11的性质可以快速构造合法数对。1. 问题等价转化目标找到正整数b , c b,cb,c满足b ⊕ c a b \oplus c ab⊕ca。异或的性质若固定b bb则c a ⊕ b c a \oplus bca⊕b。因此只需选择一个合适的b bb使得c cc也为正整数且在题目范围内。2. 构造方法记lowbit ( a ) a ( − a ) \text{lowbit}(a) a \,\\,(-a)lowbit(a)a(−a)即a aa的二进制表示中最低位的1 11。一般情况取b lowbit ( a ) b \text{lowbit}(a)blowbit(a)。因为a ≥ 1 a \ge 1a≥1所以b ≥ 1 b \ge 1b≥1。此时c a ⊕ b c a \oplus bca⊕b相当于把a aa的最低位的1 11清成0 00故c cc仍为正整数且b ⊕ c a b \oplus c ab⊕ca成立。特殊情况当a aa是2 22的幂次时即二进制中只有一个1 11lowbit ( a ) a \text{lowbit}(a)alowbit(a)a此时c 0 c0c0不满足正整数要求。此时改取b 1 b1b1则c a ⊕ 1 ca \oplus 1ca⊕1因为a ≥ 2 a \ge 2a≥2所以c ≥ 1 c \ge 1c≥1且异或结果仍为a aa。a 1 a1a1的极端情况无论取b 1 b1b1还是b lowbit ( 1 ) 1 b\text{lowbit}(1)1blowbit(1)1都有c 0 c0c0故需单独处理直接输出b 2 , c 3 b2,c3b2,c3满足2 ⊕ 3 1 2 \oplus 3 12⊕31。3. 算法步骤读入T TT组数据每组读入a aa。若a 1 a 1a1输出2 3。否则计算b lowbit ( a ) b \text{lowbit}(a)blowbit(a)。若b ≠ a b \neq aba输出b bb和a ⊕ b a \oplus ba⊕b若b a b aba即a aa是2 22的幂输出1 11和a ⊕ 1 a \oplus 1a⊕1。4. 复杂度分析时间复杂度每组数据仅进行常数次位运算O ( 1 ) O(1)O(1)。总复杂度O ( T ) O(T)O(T)T ≤ 10 5 T \le 10^5T≤105完全可行。空间复杂度O ( 1 ) O(1)O(1)仅使用几个变量。总结利用最低位1 11的位运算性质将a aa拆分为两个正整数的异或。对2 22的幂次特判避免了结果为零的情况。构造过程简单高效满足题目要求输出任意合法解。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;#definelb(x)((x)(-(x)))voidsol(){ll x;cinx;if(x1){cout2 3\n;return;}ll blb(x),cx^b;if(bx)cout1 (x^1)\n;elsecoutb c\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cint;while(t--)sol();return0;}
异或故事时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定t tt组询问76 7676每次询问都会给出一个正整数a aa你需要在区间[ 1 , 10 9 ] [1, 10^9][1,109]中找到两个正整数b bb和c cc使得b ⊕ c a b \oplus c ab⊕ca。⊕ 代表按位异或。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≤ T ≤ 10 5 ) T\ (1 \le T \le 10^5)T(1≤T≤105)代表数据组数每组测试数据描述如下在一行上输入一个整数a ( 1 ≤ a ≤ 10 9 ) a\ (1 \le a \le 10^9)a(1≤a≤109)代表76 7676给出的初始数字。输出描述对于每一组测试数据在一行上输出两个正整数代表你找到的两个值。如果存在多个解决方案您可以输出任意一个。示例 1输入3 1 5 4输出2 3 3 6 74 78说明对于第一组测试数据( 10 ) 2 xor ( 11 ) 2 ( 01 ) 2 (10)_2 \mathbin{\text{xor}} (11)_2 (01)_2(10)2xor(11)2(01)2对于第二组测试数据( 011 ) 2 xor ( 110 ) 2 ( 101 ) 2 (011)_2 \mathbin{\text{xor}} (110)_2 (101)_2(011)2xor(110)2(101)2。解题思路本题是位运算构造问题。给定正整数a aa需要在[ 1 , 10 9 ] [1,10^9][1,109]内找出两个正整数b , c b,cb,c使得b ⊕ c a b \oplus c ab⊕ca。利用二进制中最低位1 11的性质可以快速构造合法数对。1. 问题等价转化目标找到正整数b , c b,cb,c满足b ⊕ c a b \oplus c ab⊕ca。异或的性质若固定b bb则c a ⊕ b c a \oplus bca⊕b。因此只需选择一个合适的b bb使得c cc也为正整数且在题目范围内。2. 构造方法记lowbit ( a ) a ( − a ) \text{lowbit}(a) a \,\\,(-a)lowbit(a)a(−a)即a aa的二进制表示中最低位的1 11。一般情况取b lowbit ( a ) b \text{lowbit}(a)blowbit(a)。因为a ≥ 1 a \ge 1a≥1所以b ≥ 1 b \ge 1b≥1。此时c a ⊕ b c a \oplus bca⊕b相当于把a aa的最低位的1 11清成0 00故c cc仍为正整数且b ⊕ c a b \oplus c ab⊕ca成立。特殊情况当a aa是2 22的幂次时即二进制中只有一个1 11lowbit ( a ) a \text{lowbit}(a)alowbit(a)a此时c 0 c0c0不满足正整数要求。此时改取b 1 b1b1则c a ⊕ 1 ca \oplus 1ca⊕1因为a ≥ 2 a \ge 2a≥2所以c ≥ 1 c \ge 1c≥1且异或结果仍为a aa。a 1 a1a1的极端情况无论取b 1 b1b1还是b lowbit ( 1 ) 1 b\text{lowbit}(1)1blowbit(1)1都有c 0 c0c0故需单独处理直接输出b 2 , c 3 b2,c3b2,c3满足2 ⊕ 3 1 2 \oplus 3 12⊕31。3. 算法步骤读入T TT组数据每组读入a aa。若a 1 a 1a1输出2 3。否则计算b lowbit ( a ) b \text{lowbit}(a)blowbit(a)。若b ≠ a b \neq aba输出b bb和a ⊕ b a \oplus ba⊕b若b a b aba即a aa是2 22的幂输出1 11和a ⊕ 1 a \oplus 1a⊕1。4. 复杂度分析时间复杂度每组数据仅进行常数次位运算O ( 1 ) O(1)O(1)。总复杂度O ( T ) O(T)O(T)T ≤ 10 5 T \le 10^5T≤105完全可行。空间复杂度O ( 1 ) O(1)O(1)仅使用几个变量。总结利用最低位1 11的位运算性质将a aa拆分为两个正整数的异或。对2 22的幂次特判避免了结果为零的情况。构造过程简单高效满足题目要求输出任意合法解。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;#definelb(x)((x)(-(x)))voidsol(){ll x;cinx;if(x1){cout2 3\n;return;}ll blb(x),cx^b;if(bx)cout1 (x^1)\n;elsecoutb c\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cint;while(t--)sol();return0;}
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
