Я свел головоломку к следующим уравнениям:
a-b=c c<=10^9
d-e=f f<=10^9
a+b+d+e=2^k-1 where k belongs to the interval [1,33] hence atmost 33 possible sum values
a&b=0
d&e=0
Поскольку задача включает в себя как логические операции, так и арифметику c Мне трудно найти правильное решение. Наивной грубой силой я могу найти решение, перебирая a <= c и находя такое b, у которого есть & & b = 0, а затем перебирая все k и находя все возможные решения для переменных (если это возможно). Однако сложность времени будет 10 ^ 9, что плохо. Я подумал о том, чтобы работать немного. В уравнении ab = c скажем, c имеет lsb 0, тогда b должно иметь lsb 0, и, следовательно, я бы снова решил для b / 2, c / 2, однако, когда c имеет lsb 1, тогда у меня есть два варианта и тогда я должен был бы решить для b / 2, c / 2 для одного и b / 2 + 1, c / 2 для другого, следовательно, в худшем случае это может привести к 2 ^ (число бит) или 10 ^ 9. Как я могу решить это? Какие-либо предложения ? </p>