UVa 12444

題目

http://domen111.github.io/UVa-Easy-Viewer/?12444

給你兩個正整數 $C, D$，其中 $C = A \texttt{ & } B \quad D = A \texttt{ | } B$

求兩個正整數 $A, B$ 符合以上條件，並且 $B-A$ 為最小， $A \leq B$

如果沒有任何數字符合以上條件則輸出 $-1$

想法

要找到兩個數字 $A, B$ 同時符合 $A \texttt{ & }B = C$ 和 $A \texttt{ | } B = D$，那麼至少 $C$ 在二進為底下有 $1$ 的 bit 在 $D$ 上面也要有，所以如果不符合就保證無解

接下來要找到使得 $B-A$ 為最小，那麼我們可以這樣想

比較高位的 bit 必定會比所有比他低位的還大，例如說 $100_{(2)}$ 必定大於 $011_{(2)}$

所以我們只要把最高位的給 $B$，剩下的都給 $A$，那麼兩個一定會是最接近的，也符合 $A \leq B$ 的條件

Code

//By Koios1143
#include<iostream>
#include<cmath>
using namespace std;
int T, C, D, A, B, tmp, highest;
int main(){
	cin>>T;
	while(T--){
		cin>>C>>D;
		// 先判斷不符合條件的
		if((C&D) != C){
			cout<<"-1\n";
		}
		else{
			A = B = C;
			// 透過 xor 可以找到哪些位置需要看
			tmp = C^D;
			// 最高位的要給 B，可以用 log 取整得到
			highest = log2(C^D);
			for(int i=0 ; i<=highest ; i++){
				if((tmp & (1<<i)) != 0){
					if(i == highest){
						B |= (1<<i);
					}
					else{
						A |= (1<<i);
					}
				}
			}
			cout<<A<<" "<<B<<"\n";
		}
	}
	return 0;
}

時間複雜度分析

每筆測資輸入以及輸出時間複雜度均為 $O(1)$

每筆測資找答案的時間複雜度為 $O(log_{2}{(C \oplus D)})$

總時間複雜度為 $O(T(log_{2}{(C \oplus D)}))$