Soluție HackerRank pentru Fibonacci GCD, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Fibonacci GCD
- Domeniu: Number Theory
- Limbaj: C++14
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
Cerință
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, …, a_N which contains N elements.
We want to find gcd(F_a_1,F_a_2,F_a_3, ·s ,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 ≤ N ≤ 2 × 10^5
1 ≤ a_i ≤ 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 sursă
#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;
}