Submission #18897096


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

const bool ready = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();

using ld=long double;
const ld PI = acos(-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) ld d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<ld, ld>;
using vd= vector<ld>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;

#define endl "\n"


 int MOD=1e9+7;

int modInverse(int a, int m) 
{ 
    int m0 = m; 
    int y = 0, x = 1; 
  
    if (m == 1) 
        return 0; 
  
    while (a > 1) { 
        // q is quotient 
        int q = a / m; 
        int t = m; 
  
        // m is remainder now, process same as 
        // Euclid's algo 
        m = a % m, a = t; 
        t = y; 
  
        // Update y and x 
        y = x - q * y; 
        x = t; 
    } 
  
    // Make x positive 
    if (x < 0) 
        x += m0; 
  
    return x; 
} 
int mul(const int v1, const int v2, int mod=MOD) {
    return (int)((1LL * v1 * v2) % mod);
}

/* int pow */
int toPower(int a, int p, int mod=MOD) {
    int res = 1;
    while (p != 0) {
        if (p & 1)
            res = mul(res, a, mod);
        p >>= 1;
        a = mul(a, a, mod);
    }
    return res;
}

int inv(const int x, const int mod=MOD) {
    return modInverse(x,mod);
}
  
/*
 * Linear Congruence Equation, see
 * https://cp-algorithms.com/algebra/linear_congruence_equation.html
 *
 * It is that if
 * a*x=b        |mod n
 * Then:
 * x=b*inv(a)   |mod n
 * -1 for no solution
 */

/* needs Inv.cc */
int lce(int a, int b, int mod=MOD) {
    int g=__gcd(a,mod);
    if(g!=1) {
        if(b%g!=0)
            return -1LL;    /* no solution */
        a/=g;
        b/=g;
        mod/=g;
    }
    return mul(b, inv(a, mod),mod);
}

/*
 * throne=0;
 * pos=s
 * pos=(pos+k)%n
 *
 * When pos becomes 0?
 * There is most likely some stupid formular :/
 * This is somehow extended euklid...
 * It is CRM with only one formular.
 * So simple. How those this work?
 *
 * Linear congruence equation:
 * x*k=n-s           | mod n
 */
void solve() {
    cini(n);
    cini(s);
    cini(k);
    MOD=n;
    int ans=lce(k, n-s, n);
    cout<<ans<<endl;
}

signed main() {
    cini(t);
    while(t--)
        solve();
}

Submission Info

Submission Time
Task E - Throne
User nagaraj41
Language C++ (GCC 9.2.1)
Score 500
Code Size 2753 Byte
Status AC
Exec Time 8 ms
Memory 3604 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 1
AC × 32
Set Name Test Cases
Sample sample_01.txt
All hand_01.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt
Case Name Status Exec Time Memory
hand_01.txt AC 8 ms 3436 KB
random_01.txt AC 3 ms 3504 KB
random_02.txt AC 4 ms 3496 KB
random_03.txt AC 4 ms 3540 KB
random_04.txt AC 2 ms 3600 KB
random_05.txt AC 3 ms 3484 KB
random_06.txt AC 6 ms 3500 KB
random_07.txt AC 2 ms 3524 KB
random_08.txt AC 2 ms 3564 KB
random_09.txt AC 2 ms 3604 KB
random_10.txt AC 3 ms 3560 KB
random_11.txt AC 2 ms 3432 KB
random_12.txt AC 3 ms 3452 KB
random_13.txt AC 2 ms 3500 KB
random_14.txt AC 6 ms 3440 KB
random_15.txt AC 3 ms 3504 KB
random_16.txt AC 3 ms 3560 KB
random_17.txt AC 2 ms 3556 KB
random_18.txt AC 2 ms 3508 KB
random_19.txt AC 3 ms 3520 KB
random_20.txt AC 3 ms 3552 KB
random_21.txt AC 2 ms 3500 KB
random_22.txt AC 2 ms 3544 KB
random_23.txt AC 3 ms 3544 KB
random_24.txt AC 2 ms 3496 KB
random_25.txt AC 3 ms 3496 KB
random_26.txt AC 3 ms 3552 KB
random_27.txt AC 2 ms 3492 KB
random_28.txt AC 2 ms 3560 KB
random_29.txt AC 2 ms 3508 KB
random_30.txt AC 4 ms 3504 KB
sample_01.txt AC 2 ms 3592 KB