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 * b_i + a_i * a_i)\) mod 3001

\(b_{i+1} = (k * 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 * b_i + a_i * a_i)\) mod 3001 and \(b_{i+1} = (k * 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 \leq K \leq 3000\)

\(0 \leq T \leq 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