e305 - Xor 運算
題目描述
題目要求計算 sumxor(N) 的值，其中 sumxor(N) 定義為從 0 到 N-1 的整數中，滿足 (N ^ i) == (N + i) 的 i 的數量。由於 N 的範圍較大，直接迴圈計算會超時，因此需要優化演算法。
解題思路
觀察 (N ^ i) == (N + i) 這個條件。將其展開，得到 N ^ i == N + i，等價於 i == N ^ (N + i)。由於 N ^ (N + i) = N ^ N + N ^ i = 0 + N ^ i = N ^ i，所以 i == N ^ (N + i) 總是成立。因此，N ^ i == N + i 簡化為 i == 0。
所以，sumxor(N) 的值實際上是滿足 i == 0 的 i 的數量，在 0 <= i < N 的範圍內，只有 i = 0 滿足條件。因此，sumxor(N) 的值永遠是 1，除非 N 等於 0，此時 sumxor(N) 的值是 0。
程式碼直接根據這個簡化的邏輯進行計算，避免了迴圈，從而提高了效率。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline void write(long long int x) {
if(x==0){
putchar_unlocked('0');
return;
}
long long int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
inline long long int sumxor(long long int N){
if(!N)return 0;
long long int ans=1;
while(N){
if(N%2==0)ans<<=1;
N/=2;
}
return ans;
}
int main(){
char c;
long long int n=0;
while(c=getchar_unlocked()){
if(c==-1)
break;
if(c<'0'){
write(sumxor(n));
putchar_unlocked('\n');
n=0;
}
else{
n*=10;
n+=c-48;
}
}
}