Enésimo número de Fibonacci XOR

Dados tres enteros a , b y N donde a y b son los dos primeros términos de la serie XOR de Fibonacci y la tarea es encontrar el N ^-ésimo término. 
El término N de la serie XOR de Fibonacci se define como F(N) = F(N – 1) ^ F(N – 2) donde ^ es el XOR bit a bit.
Ejemplos: 
 

Entrada: a = 1, b = 2, N = 5 
Salida: 3 
F(0) = 1 
F(1) = 2 
F(2) = 1 ^ 2 = 3 
F(3) = 2 ^ 3 = 1 
F( 4) = 1 ^ 3 = 2 
F(5) = 1 ^ 2 = 3
Entrada: a = 5, b = 11, N = 1000001 
Salida: 14 
 

Planteamiento: Ya que, a^a = 0 y se da que 
 

F(0) = a y F(1) = b 
Ahora, F(2) = F(0) ^ F(1) = a ^ b 
Y, F(3) = F(1) ^ F(2) = b ^ (a ^ b) = a  
F(4) = a ^ b ^ a = b  
F(5) = a ^ b  
F(6) = a  
F(7) = b  
F(8) = a ^ b 
… 
 

Se puede observar que la respuesta se repite cada 3 números. Entonces la respuesta es F(N % 3) donde F(0) = a, F(1) = b y F(2) = a ^ b .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the nth XOR Fibonacci number
int nthXorFib(int n, int a, int b)
{
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    if (n == 2)
        return (a ^ b);
 
    return nthXorFib(n % 3, a, b);
}
 
// Driver code
int main()
{
    int a = 1, b = 2, n = 10;
 
    cout << nthXorFib(n, a, b);
 
    return 0;
}

// Java implementation of the above approach
class GFG
{
         
    // Function to return the
    // nth XOR Fibonacci number
    static int nthXorFib(int n, int a, int b)
    {
        if (n == 0)
            return a;
        if (n == 1)
            return b;
        if (n == 2)
            return (a ^ b);
     
        return nthXorFib(n % 3, a, b);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int a = 1, b = 2, n = 10;
     
        System.out.println(nthXorFib(n, a, b));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return
# the nth XOR Fibonacci number
def nthXorFib(n, a, b):
    if n == 0 :
        return a
    if n == 1 :
        return b
    if n == 2 :
        return a ^ b
 
    return nthXorFib(n % 3, a, b)
 
# Driver code
a = 1
b = 2
n = 10
print(nthXorFib(n, a, b))
 
# This code is contributed by divyamohan123

// C# implementation of the above approach
using System;
     
class GFG
{
         
    // Function to return the
    // nth XOR Fibonacci number
    static int nthXorFib(int n, int a, int b)
    {
        if (n == 0)
            return a;
        if (n == 1)
            return b;
        if (n == 2)
            return (a ^ b);
     
        return nthXorFib(n % 3, a, b);
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        int a = 1, b = 2, n = 10;
     
        Console.WriteLine(nthXorFib(n, a, b));
    }
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript implementation of the approach
 
// Function to return the nth XOR Fibonacci number
function nthXorFib(n, a, b)
{
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    if (n == 2)
        return (a ^ b);
 
    return nthXorFib(n % 3, a, b);
}
 
// Driver code
    let a = 1, b = 2, n = 10;
 
    document.write(nthXorFib(n, a, b));
 
</script>

2

Complejidad de tiempo: O(1)