UVa - 11053 - Flavius Josephus Reloaded

11053.cpp

/**
  Solution using Floyd's Tortoise and Hare Algorithm
 **/
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define PB push_back
#define endl '\n'

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;
typedef set<int>::iterator sit;

int f(int a, int b, int x, int n) {
    int sol = ((a % n) * (((1LL * x) * x) % n)) % n;
    sol = (sol + b) % n;
    return sol;
}

ii floyd(int a, int b, int n, int x0) {
    int tortoise = f(a, b, x0, n);
    int hare = f(a, b, f(a, b, x0, n), n);
    
    while(tortoise != hare) {
        tortoise = f(a, b, tortoise, n);
        hare = f(a, b, f(a, b, hare, n), n);
    }

    int mu = 0; hare = x0;
    while(tortoise != hare) {
        tortoise = f(a, b, tortoise, n);
        hare = f(a, b, hare, n);
        mu++;
    }

    int lambda = 1; hare = f(a, b, tortoise, n);
    while(tortoise != hare) {
        hare = f(a, b, hare, n);
        lambda++;
    }

    return ii(mu, lambda);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, a, b, sol, x;
    while(cin >> n >> a >> b) {
        if(n == 0) break;

        int sol = (floyd(a, b, n, x)).S;
        cout << (n - sol) << endl;
    }

    return 0;
}