Contest Duration: - (local time) (100 minutes) Back to Home

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 2020-12-20 01:30:39+0900 E - Throne nagaraj41 C++ (GCC 9.2.1) 500 2753 Byte AC 8 ms 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