D_Riberto_s_Function.cpp

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef map<ll, ll> mll;
typedef set<ll> sll;
typedef queue<ll> qll;
typedef queue<pll> qpll;

#define all(x) x.begin(), x.end()
#define sz(x) (ll) x.size()
#define fr front()
#define bk back()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define FOR(i, a, b, inc) for (ll i = a; i < b; i += inc)
#define RFOR(i, a, b, inc) for (ll i = b - 1; i >= a; i -= inc)
#define REP(i, a) FOR(i, 0, a, 1)
#define RREP(i, a) RFOR(i, 0, a, 1)
#define each(a, x) for (auto& a: x)

const ll INF = 1e9;
const ll M = 1e9 + 7;

ll A, B, C, x, k; 

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}
ll pow(ll a, ll b) {
    if (b == 0) return 1;
    if (b == 1) return a;
    ll x = pow(a, b/2);
    if (b%2 == 0) return x*x;
    return x*x*a;
}

ll f(ll x) {
    return abs(A*x + B) % C;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll t; cin >> t;
    while (t--) {
        cin >> A >> B >> C >> x >> k;

        vll v;
        map<ll, ll> m;
        
        ll startOfCycle;
        for (ll i=0; ; i++) {
            x = f(x);
            
            if (m[x]) {
                startOfCycle = m[x];
                break;
            }
            
            v.pb(x);
            m[x] = i;
        }
        
        if (k - 1 < startOfCycle) {
            cout << v[k - 1] << '\n';
        } else {
            k -= startOfCycle;
            k--;
            
            ll sizeOfCycle = sz(v) - startOfCycle;
            k %= sizeOfCycle;
            
            cout << v[startOfCycle + k] << '\n';
        }
    }
}