Simple Recursive Sequence - HackerEarth Solution

Simple Recursive Sequence - HackerEarth Solution

Simple Recursive Sequence - HackerEarth Solution

Simple Recursive Sequence

The $K$-fantastic sequence is define in the following way:

$a_{i+1}=(k\ast b_i+a_i\ast a_i)$ mod 3001

$b_{i+1}=(k\ast a_i+b_i)$ mod 3001

$a_0=1$

$b_0=2$

Find the $T$-th pair of numbers of the $K$-fantastic sequence

Example

Consider K = 2 and T = 2,

as $(a_0,b_0)=(1,2)$, using $a_{i+1}=(k\ast b_i+a_i\ast a_i)$ mod 3001 and $b_{i+1}=(k\ast a_i+b_i)$ mod 3001,

then we get $(a_1,b_1)=(5,4)$,

then we get $(a_2,b_2)=(33,14)$.

Function description

Complete the Simple_Recursive_Sequence function provided in the editor. This function takes the following 2 parameters and returns an array containing $a_T$ and $b_T$:

• K: An Integer representing value of K.
• T: An Integer representing value of T.

Input format

• First line: Two space-separated integers $K$ and $T$

Ouput format

Print $a_T$ and $b_T$

Constraints

$0\le K\le 3000$

$0\le T\le {10}^9$

Simple Recursive Sequence - HackerEarth Solution

Solution - 

#include <bits/stdc++.h>

using namespace std;

#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#define t_times int t; cin >> t; while(t--)

 

long long n, k;

const int m = 3001;

int vis[m][m];

void _solve() {

    cin >> k >> n;

    assert(k >= 0 && k <= 3000);

    assert(n >= 0 && n <= 1000000000);

    int a = 1, b = 2, next_a, next_b, cnt = 1, period = -1;

    vis[a][b] = 1;

    vector< pair< int, int>> v {{a, b}};

    for(int i = 1; i <= m * m; i++) {

        next_a = (k * b + a * a) % m;

        next_b = (k * a + b) % m;

        a = next_a, b = next_b;

        v.push_back({a, b});

        if(vis[a][b]) {

            period = cnt - vis[a][b] + 1;

            cnt = vis[a][b];

            break;

        }

        vis[a][b] = ++cnt;

    }

    //cout << cnt << ' ' << period << '\n';

    assert(period != -1);

    int pos = n;

    if(n > cnt) pos = cnt + ((n - cnt) % period);

    cout << v[pos].first << ' ' << v[pos].second << '\n';

}

 

int main() {

    fastio;

    //t_times

    _solve();

    return 0;

}

Simple Recursive Sequence - HackerEarth Solution

Disclaimer: The above Problem is generated by HackerEarth but the Solution is Provided by Us. This tutorial is only for Educational and Learning purposes. Authority if any of the queries regarding this post or website contact us on coderinme.net@gmail.com .

For DMCA: https://allhackerranksolutionsbykaira.blogspot.com/p/dmca.html