#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];
ll prev_a = a;
for (int i=1; i<(int)rem.size(); i++) {
ll x, y;
ll d = ext_gcd(M, mod[i], x, y);
ll diff = rem[i]-a;
ll m_div = mod[i]/d;
// Calculate k and ensure it's within bounds
ll k = ((diff / d) % m_div) * (x % m_div) % m_div;
if (k < 0) k += m_div;
// Check for overflow in a + k*M
ll delta = k * M;
if (delta > 0 && a > LLONG_MAX - delta)
return prev_a;
ll new_a = a + delta;
ll new_M = M / d * mod[i];
new_a %= new_M;
if (new_a < 0) new_a += new_M;
if (new_a > 1e18)
return prev_a;
prev_a = a;
a = new_a;
M = new_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
}
