Help in Atcoder regular contest 066 problem B, Xor Sum.

Revision en4, by spirited_away_, 2019-06-21 01:23:43

Given a number N, The problem asks you to find all such pairs u,v such that there exists another set of pairs a,b such that

  1. a ^ b = u

  2. a + b = v

where u , v <= N.

I finally concluded that basically we have to find a+b<=N, but how to proceed from here. Can we use counting principle to solve this problem, i mean count all a+b == N and a+b < N and to avoid repeatation we will considere a >= b.

Can anyone tell me the approach and intutition to solve it. Editorial is in japanese.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English spirited_away_ 2019-06-21 01:23:43 134
en3 English spirited_away_ 2019-06-21 01:01:59 2 Tiny change: 'uch that\n1. a ^ b' -> 'uch that\n\n1. a ^ b'
en2 English spirited_away_ 2019-06-21 01:01:22 6 Tiny change: '(https://abc050.contest.a' -> '(https://arc066.contest.a'
en1 English spirited_away_ 2019-06-21 01:00:46 531 Initial revision (published)