HackerRank Number Theory – Fibonacci GCD

Challenge: Fibonacci GCD

Subdomeniu: Number Theory (number-theory)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464759180

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/fibonacci-gcd/problem

Cerinta

Fibonacci numbers have the following form:  
$$F_1 = 1 \\\
F_2 = 1 \\\
F_3 = 2 \\\
\vdots \\\
F_n = F_{n-2}+F_{n-1}$$  

We have an array $a_1, a_2, \ldots, a_N$ which contains $N$ elements.   

We want to find $\gcd(F_{a_1},F_{a_2},F_{a_3}, \cdots ,F_{a_N} )$.  

**Input Format**  
The first line contains $N$, where $N$ denotes size of the array.  
Each of the next $N$ lines contains a number: the $i^{\text{th}}$ line contains $a_i$.

**Output Format**  
Print a single integer — the remainder of the division of the resulting number by $10^9+7$.  

**Constraints**  
$1 \le N \le 2 \times 10^5$   
$1 \le a_i \le 10^{12}$  


**Sample Input 1**

    3
    2
    3
    5

**Sample Output 1**

    1

**Explanation 1**  
$F_2 = 1$  
$F_3 = 2$  
$F_5 = 5$   
$\gcd(1,2,5)=1$  


**Sample Input 2**

    2
    3
    6

**Sample Output 2**

    2

**Explanation 2**  
$F_3 = 2$  
$F_6 = 8$  
$\gcd(2,8)=2$

Cod sursa

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007LL;

pair<long long,long long> fib(long long n) {
    if (n == 0) return {0, 1};
    auto p = fib(n >> 1);
    long long a = p.first;  // F(k)
    long long b = p.second; // F(k+1)

    long long c = (__int128)a * ((2 * b % MOD - a + MOD) % MOD) % MOD; // F(2k)
    long long d = ((__int128)a * a + (__int128)b * b) % MOD;           // F(2k+1)

    if (n & 1) return {d, (c + d) % MOD};
    return {c, d};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long g = 0;
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        g = __gcd(g, x);
    }

    cout << fib(g).first % MOD << '\n';
    return 0;
}