Как бы вы нашли XOR всех целых чисел в диапазоне от l до r, где - (10 ^ 18) <= l, r <= 10 ^ 18? - PullRequest
Новая
       25

Как бы вы нашли XOR всех целых чисел в диапазоне от l до r, где - (10 ^ 18) <= l, r <= 10 ^ 18?

0 голосов
/ 26 октября 2019

Я знаю, что именно так вы бы это реализовали, когда 1 <= l, r <= 10 ^ 18, но как бы вы справились с отрицательным числом? </p> 

long long int xorf(long long int n){
    long long int mod=n%4;
    switch(mod){
        case 0:return n;
            break;
        case 1:return 1;
            break;
        case 2:return n+1;
            break;
        case 3:return 0;
            break;
    }
    int main(){
    long long int l,r;
    long long int xo=0;
        cin>>l>>r;
        xo = (xorf(l-1)^xorf(r));
        cout<<xo<<endl;
    }

1 Ответ

0 голосов
/ 26 октября 2019

Если n> = 0, тогда (как вы говорите) 1 ^ 2 ^ ... ^ n можно вычислить как: 

long long PositiveXor(long long n){
  switch (n % 4){
        case 0: return n ;
        case 1: return 1 ;
        case 2: return n+1 ;
        case 3: return 0 ;
    }
}

Аналогично, если n < 0, то n ^ (n+1) ^ ... ^ -1 можно вычислить как: 

long long NegativeXor(long long n){
  switch ((-n) % 4){
        case 0: return 0 ;
        case 1: return n ;
        case 2: return 1 ;
        case 3: return n-1 ;
    }
}

(Это предполагает представление дополнения до 2).

Так что если l >= 0, ответ будет PositiveXor(r) ^ PositiveXor(l-1);и если l < 0 и r >= 0, ответ будет NegativeXor(l) ^ PositiveXor(r). Я оставлю третий случай (r < 0) на ваше усмотрение.

...