#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
vector<pii> Alice(){
ll x = setN(5000);
vector<pii> edges;
for (int i=1; i<5000; i++){
int v = x%i;
edges.push_back({v+1, i});
}
return edges;
}
#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
ll ext_gcd(ll a, ll b, ll &x, ll &y){
if (!b) { x = 1; y = 0; return a; }
ll g = ext_gcd(b, a % b, y, x);
y -= a / b * x;
return g;
}
ll crt(vector<ll> rem, vector<ll> mod){
ll a = rem[0], M = mod[0];
for (int i=1; i<(int)rem.size(); i++) {
ll x, y, d = ext_gcd(M, mod[i], x, y);
ll diff = rem[i] - a;
ll k = (diff / d * x) % (mod[i] / d);
if (k < 0) k += mod[i] / d;
a += k * M;
M = M / d * mod[i];
a = (a % M + M) % M;
}
return a;
}
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
ll Bob(vector<pii> V){
vector<ll> rem, mod;
for (auto [r, m] : V){
r--, rem.push_back(r);
mod.push_back(m);
}
ll x = crt(rem, mod);
return x; // change this into your code
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |