Submission #18879409

---

Source Code Expand

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#pragma GCC optimize("O3")
#include <atcoder/math>
#include<bits/stdc++.h>
using namespace atcoder;

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

ll GCD(ll x, ll y) {
    if (y == 0) {
        return x;
    }
    return GCD(y, x % y);
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#else
//    freopen("lupa.in","r",stdin);
//    freopen("pupa.out","w",stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(10);
    cout << fixed;
    int T;
    cin >> T;
    while (--T >= 0) {
        int n, pos, k;
        cin >> n >> pos >> k;
        pos = (n - pos) % n;
        ll gcd = GCD(n, k);
        if (pos % gcd != 0) {
            cout << -1;
        } else {
            n /= gcd;
            k /= gcd;
            pos /= gcd;
            ll ans = pos * inv_mod(k, n);
            ans %= n;
            cout << ans;
        }
        cout << '\n';
    }
    return 0;
}

Submission Info

Judge Result