Ideone.com

download

copy

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 111539786;
 
map <ll, ll> f;
 
ll get(ll n)
{
    if (f.count(n)) return f[n];
    ll k=n / 2;
    if (!(n % 2))
        return f[n]=(get(k)*get(k) + get(k-1)*get(k-1)) % mod;
    else
        return f[n]=(get(k)*get(k+1) + get(k-1)*get(k)) % mod;
}
main()
{
    int t, n;
    cin>>t;
    while (t--)
    {
        cin>>n;
        f[0]=f[1]=1;
        cout<<get(n)<<endl;
    }
}

Runtime error #stdin #stdout 0s 16064KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/aZhwVM

language:

C++ (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language