首页 > 其他分享 >Codeforces Round #847 (Div. 3)

Codeforces Round #847 (Div. 3)

时间:2023-01-28 10:55:48浏览次数:51  
标签:847 le cdot tt Codeforces tag Div oplus

E. Vlad and a Pair of Numbers

题目抽象为给 \(n\) \((1\le n\le 2^{29})\),求 \(x\) 满足 \((n-x)\oplus (n+x)=n\),输出 \(n-x\) 和 \(n+x\)。

显然 \(n\) 为奇数肯定不行。

记 \(a=n-x,b=n+x\),由位运算的性质有 \(a+b=a\oplus b+2\cdot (a\& b)\)。

\[a+b=a\oplus b+2\cdot (a\& b) \tag{1} \]

\[\frac{a+b}{2}=a\oplus b \tag{2} \]

由 (\(1\)) (\(2\)) 可得:

\[a\oplus b=2\cdot (a\&b)=n \]

\[\frac{a+b}{2}=2\cdot (a\& b) \]

那么可以让 \(a=(a\&b),b=3\cdot (a\&b)\)。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
  int n;
  cin >> n;
  if (n % 2 == 1) {
    cout << -1 << '\n';
    return;
  }
  int a = n / 2;
  int b = 3 * a;
  if ((a + b) / 2 != (a ^ b)) {
    cout << -1 << '\n';
  } else {
    cout << a << ' ' << b << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

标签:847,le,cdot,tt,Codeforces,tag,Div,oplus
From: https://www.cnblogs.com/kiddingma/p/17069826.html

相关文章

  • CF 1790E. Vlad and a Pair of Numbers_Codeforces Round #847 (Div. 3)
    给出整数x,求一对整数(a,b),满足:\(a\bigoplusb=x\),\(\frac{a+b}{2}=x\)(\(\frac{a+b}{2}\)不四舍五入,也就是\(2\mida+b\))如果不存在这样的(a,b)输出-1分析:如果x的最......
  • # CF#847 (Div. 3)ABCDE题解
    CodeforcesRound#847(DFiv.3)APolycarpandtheDayofPiProblem-A-Codeforces题目描述OnMarch14,thedayofthenumber$\pi$iscelebratedallov......
  • Educational Codeforces Round 2 个人总结A-E
    EducationalCodeforcesRound2A.ExtractNumbers简单的模拟boolcheck(stringop){ if(op.size()==1&&op[0]=='0') returntrue; if(op.size()==0||(op[0]<'1......
  • #0031. Educational Codeforces Round 1
    AB简单题C是计算几何,但核心解法很像sgnoi某年的t1,即与其考虑所有pairs,不如只考虑所有相邻的,这样复杂度就从\(O(N^2)\)降到了O(N)(如果不考虑排序的复杂度的话)。不过这......
  • Educational Codeforces Round 142
    目录写在前面ABCDE写在最后写在前面比赛地址:https://codeforces.com/contest/1792。我是超级大鸽子咕咕咕A当且仅当有两个怪物初始血量为1时使用操作1,否则用操作2......
  • Codeforces Round #846 (Div. 2)
    题目链接D题意给定一个数字n,我们需要通过一系列的操作去猜测这个数字。初始的时候会给我们一个cnt,表示二进制下数字n有多少个1.每次我们可以给出一个t,然后另n减去t,系统......
  • Codeforces Round #601 (Div. 2) A-E
    比赛链接A题意给两个数字\(a,b\),每次操作可以使\(a\)加上\(+1,+2,+5,-1,-2,-5\)中的一个数,求最少多少次操作可以将\(a\)变成\(b\)。题解知识点:贪心。可以......
  • CodeForces 1415E New Game Plus!
    洛谷传送门CF传送门相当于将\(n\)个数分成\(k+1\)组,将每组的最大收益相加。容易发现组内的数不增最优。考虑开个堆,维护当前\(k+1\)组的和即可。code/*p_b_......
  • CodeForces 1415D XOR-gun
    洛谷传送门CF传送门纯纯的诈骗。下文令\(f(x)\)为\(x\)最高位使得这一位为\(1\)。考虑若存在\(i\in[1,n-2]\)使得\(f(a_i)=f(a_{i+1})=f(a_{i+2})\),那么......
  • Educational Codeforces Round 1
    A.TrickySum题意:给一个n,求1到n的运算,如果不是2的次方就加,否则减思路:由于n有1e9,直接暴力扫过去肯定要寄所以先$n*(n+1)/2$来算出1到n的和再减去2倍的2......