8VC Venture Cup 20161 627A - XOR Equation 8VC Venture Cup 2016 — Final Round A번 문제이다. (Div.1 Edition B번, Div.2 Edition C번)별로 어렵지 않은 문제인데 한참동안 해매어서 정리.두 양의 정수 a와 b의 합이 s이고 XOR한 결과가 x일 때에, 가능한 (a, b) 순서쌍의 개수를 구하는 것이 문제이다.접근법 1)a+b = s, a^b = xb = (s-a)a^(s-a) = xs-a = a^x. 양번에 a를 XOR하면 a^(s-a) = a^x여기서 잘못됨을 깨닫고 다른 관계식을 시도함.접근법 2)a^b = a+b - 2(a&b)XOR라는 연산이 두 bit가 다르면 1이기 때문에 덧셈에서 자리올림을 빼면 그 결과가 XOR와 같다는 식.정리하면 (s-x)/2 = a&b여기서 매 digit마다 (.. 2016. 3. 10. 이전 1 다음