# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1016808 | NValchanov | Magic Show (APIO24_show) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "Alice.h"
#define endl '\n'
using namespace std;
typedef long long ll;
vector < pair < int, int > > Alice()
{
int n = setN(5000);
vector < pair < int, int > > edges;
for(int i = 1; i < n; i++)
{
edges.push_back({x % i + 1, i});
}
return edges;
}
#include <bits/stdc++.h>
#include "Bob.h"
#define endl '\n'
using namespace std;
typedef long long ll;
/// EXTENDED GCD :(
pair < ll, pair < ll, ll > > extgcd(ll a, ll b)
{
if(b == 0)
return {a, {1, 0}};
pair < ll, pair < ll, ll > > g = extgcd(b, a % b);
ll d = g.first;
ll x = g.second.first;
ll y = g.second.second;
ll x1 = y;
ll y1 = x - y * (a / b);
return {d, {x1, y1}};
}
ll Bob(vector < pair < int, int > > edges)
{
/// CRT
ll l = 0;
ll ans = 0;
for(pair < int, int > e : edges)
{
ll u = e.first;
ll v = e.second;
if(u > v)
swap(u, v);
u--;
v--;
if(ans == 0)
{
ans = u;
l = v;
continue;
}
pair < ll, pair < ll , ll > > g = extgcd(l, v);
ll d = g.first;
ll x = g.second.first;
ll y = g.second.second;
ans = ans + (x * (u - ans) / d) % (v / d) * l;
l = l * v / d;
ans = (ans + l) % l;
if(l >= 1e18)
break;
}
return ans;
}