変数xのiビット目をxiとします。ai,biは0または1のどちらかなので、ai+bi=ai⊕bi+2aibiが成立します。よって、p=∑i(ai⊕bi+2aibi)2i=∑i(ai⊕bi)2i+∑i2i+1aibi=q+∑i2i+1aibiとなります。よって、p−q=dとすると、d=∑i2i+1aibiより「dのkビット目が1⇔ak−1=bk−1=1」が成立するので、ここから各ビットについて考えていきます。
iビット目について、
- qi=0, di+1=0ならばai=bi=0です。(di+1=0よりaibi=0だから)
- qi=0, di+1=1ならばai=bi=1です。(di+1=1よりaibi=1だから)
- qi=1, di+1=0ならば(ai,bi)=(1,0),(0,1)です。(ここは確定しません)
- qi=1, di+1=1ならば解なしです。(ai=bi=1がqi=1と矛盾するから)
また、最初のビットへの繰り上がりは存在しないため、d0=1ならば解なしとなります。
これらのことに注意して解を組み立てれば良いです。計算量はO(Mlogp)となりますが、今回はM≤100なので十分間に合います。
質問・誤りがある場合
Twitterに連絡ください。ID : @YS55749378