変数xxiiビット目をxix_iとします。ai,bia_i,b_i00または11のどちらかなので、ai+bi=aibi+2aibia_i+b_i=a_i\oplus b_i+2a_ib_iが成立します。よって、p=i(aibi+2aibi)2i=i(aibi)2i+i2i+1aibi=q+i2i+1aibip=\sum_i(a_i\oplus b_i+2a_ib_i)2^i=\sum_i(a_i\oplus b_i)2^i+\sum_i2^{i+1}a_ib_i=q+\sum_i2^{i+1}a_ib_iとなります。よって、pq=dp-q=dとすると、d=i2i+1aibid=\sum_i2^{i+1}a_ib_iより「ddkkビット目が1ak1=bk1=11\Leftrightarrow a_{k-1}=b_{k-1}=1」が成立するので、ここから各ビットについて考えていきます。

iiビット目について、

  • qi=0, di+1=0q_i=0,\ d_{i+1}=0ならばai=bi=0a_i=b_i=0です。(di+1=0d_{i+1}=0よりaibi=0a_ib_i=0だから)
  • qi=0, di+1=1q_i=0,\ d_{i+1}=1ならばai=bi=1a_i=b_i=1です。(di+1=1d_{i+1}=1よりaibi=1a_ib_i=1だから)
  • qi=1, di+1=0q_i=1,\ d_{i+1}=0ならば(ai,bi)=(1,0),(0,1)(a_i,b_i)=(1,0),(0,1)です。(ここは確定しません)
  • qi=1, di+1=1q_i=1,\ d_{i+1}=1ならば解なしです。(ai=bi=1a_i=b_i=1qi=1q_i=1と矛盾するから)

また、最初のビットへの繰り上がりは存在しないため、d0=1d_0=1ならば解なしとなります。

これらのことに注意して解を組み立てれば良いです。計算量はO(Mlogp)O(M\log p)となりますが、今回はM100M\leq 100なので十分間に合います。

ans.cpp

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378