Soluție HackerRank pentru Fibonacci LCM, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Fibonacci LCM
  • Domeniu: Number Theory
  • Limbaj: C++14

Challenge: Fibonacci LCM

Subdomeniu: Number Theory (number-theory)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464735141

Limbaj: cpp14

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

Cerință

After Derek (of district 5) discovered how to compute the greatest common divisor (gcd) of Fibonacci numbers, he now tried to answer the next obvious question: how does one compute the *least common multiple* (lcm) of Fibonacci numbers? Unfortunately, Derek found out that this wasn't as easy as the original problem, so he asked you to answer it for him.

The Fibonacci numbers are defined as:

F_1 = F_2 = 1
F_n = F_n-1 + F_n-2

Given N integers a_1, a_2, …, a_N, find text{lcm}(F_a_1,F_a_2,…,F_a_N), and give your answer modulo 10^9+7.

Input Format
The first line of input contains N.
Each of the next N lines contains a number: the i^{text{th}} line contains a_i.

Constraints
1 ≤ N ≤ 100
1 ≤ a_i ≤ 10^9

Output Format
Print a single integer, which is the least common multiple of the F_a_i, modulo 10^9+7.

Sample Input

5
1
3
3
6
9

Sample Output

136

Explanation
text{lcm}(F_1,F_3,F_3,F_6,F_9) = text{lcm}(1,2,2,8,34) = 136

Cod sursă

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

const int N = 3e5 + 9, mod= 1e9 + 7;

int power(long long n, long long k) {
  int ans = 1 % mod; n %= mod; if (n < 0) n += mod;
  while (k) {
    if (k & 1) ans = (long long) ans * n % mod;
    n = (long long) n * n % mod;
    k >>= 1;
  }
  return ans;
}
int fib(long long n) {
  assert (n >= 0);
  if (n <= 1) return n;
  int a = 0;
  int b = 1;
  long long i = 1ll << (63 - __builtin_clzll(n) - 1);
  for (; i; i >>= 1) {
    int na = (a *(long long) a + b *(long long) b) % mod;
    int nb = (2ll * a + b) * b % mod;
    a = na;
    b = nb;
    if (n & i) {
      int c = a + b; if (c >= mod) c -= mod;
      a = b;
      b = c;
    }
  }
  return b;
}
map<vector<int>, int> dp;
/**
O((max number of divisors of a[i]) * n * log(max a[i])) but faster in practice
lcm(a1, a2, ... an) 
= lcm(lcm(a1, ..., a[n-1]), an)
= lcm(a1, ..., a[n-1]) * an / gcd(lcm(a1, ..., a[n-1]), an)
= lcm(a1, ..., a[n-1]) * an / lcm(gcd(a1, an), ... gcd(a[n-1], an))
**/
int yo(vector<int> a) {
  sort(a.rbegin(), a.rend());
  while (!a.empty() && a.back() <= 2) a.pop_back();
  a.resize(unique(a.begin(), a.end()) - a.begin());
  if (a.empty()) return 1;
  if (a.size() == 1) return fib(a[0]);
  if (dp.count(a)) return dp[a];
  vector<int> b(a.begin(), a.end() - 1);
  long long res = yo(b);
  for (int i = 0; i < b.size(); ++i) b[i] = __gcd(b[i], a.back());
  res = res * fib(a.back()) % mod * power(yo(b), mod - 2) % mod;
  dp[a] = res;
  return res;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n; cin >> n;
  vector<int> a(n);
  for (auto &x: a) cin >> x;
  cout << yo(a) << '\n';
  return 0;
}
//https://www.hackerrank.com/contests/infinitum10/challenges/fibonacci-lcm/problem
HackerRank Number Theory – Fibonacci LCM