• + 1 comment
    /* what's wrong with this code tle problem  */
    #include<bits/stdc++.h>
    using namespace std;
    long long gcd(long long a,long long b)
    {
     if(a==0)
        return b;
      return gcd(b%a,a);
    }
    long long fib(long long c)
     {
      if(c<=1)
        return c;
      return (fib(c-1)+fib(c-2));
     }
    int main()
    {
      long long int n,ans,p,q;
      cin>>n;
       long long int a[n];
     for(int i=0;i<n;i++)
        cin>>a[i];
      ans=a[0];
      for(int i=1;i<n;i++)
      ans=gcd(ans,a[i]);
       p=fib(ans);
       cout<<p%1000000007<<endl;
    }
    
    • + 0 comments

      Working Python3 solution. Yours is "Naive Algo" which almost always gives TLE

      P = 10 ** 9 + 7
      
      from fractions import gcd
      from functools import reduce, lru_cache
      
      @lru_cache(maxsize = None)
      def fib(n):
          if n == 0:
              return 0
          if n == 1:
              return 1
          if (n & 1) == 1:
              return (fib(n // 2) * fib(n // 2) + fib(n // 2 + 1) * fib(n // 2 + 1)) % P
          else:
              return fib(n // 2) * (fib(n // 2) + 2 * fib(n // 2 - 1)) % P
      
      n = int(input())
      a = (int(input()) for _ in range(n))
      g = reduce(gcd, a, 0)
      print(fib(g))