#include <bits/extc++.h>
#include "Alice.h"
//#include "Bob.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
using namespace __gnu_pbds;
template<class T> using PBDS = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using multiPBDS = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll gcd(ll a, ll b)
{
if(a==0) return b;
if(b==0) return a;
return gcd(b, a%b);
}
ll minv(ll a, ll b)
{
if(a==0 && b==1) return 0;
if(a==1) return 1;
return b - minv(b%a, a) * b / a;
}
// x == A.first (mod A.second)
// x == B.first (mod B.second)
// returns solution as X == ans.first (mod ans.second)
// if no solution, returns (-1, -1)
// always a good idea to keep 0 <= ?.first < ?.second (for ? : A, B, ans)
pair<ll, ll> solve(pair<ll, ll> A, pair<ll, ll> B)
{
if(A.second == -1 || B.second == -1) return make_pair(-1, -1);
if(A.second == 1) return B;
if(B.second == 1) return A;
ll g = gcd(A.second, B.second); // gcd
ll l = A.second * (B.second / g); // lcm
if((B.first-A.first)%g!=0) return make_pair(-1, -1); // no solution case
ll a = A.second / g;
ll b = B.second / g;
ll mul = (B.first-A.first) / g;
mul = (mul * minv(a%b, b)) % b; // this is now t
ll ret = (mul * A.second + A.first); // n_1 t + a_1
ret %= l; ret = (ret + l) % l; // take modulos
return make_pair(ret, l);
}
vector<pint> Alice(){
ll x = setN(5000);
vector<pint> edges;
for(int i=2;i<=5000;i++) edges.push_back({x%(i-1)+1,i});
return edges;
}
//ax+by=c
//ax+by=gcd(a,b)를 만족하는 x와 y를 s와 t에 저장.
//c가 gcd(a,b)의 배수일 때만 가능 (이게 아니라면 x,y는 존재 안 함)
//gcd(a,b)가 return됨.
//log 시간
ll ex_gcd(ll a, ll b, ll& x, ll& y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll ret = ex_gcd(b, a % b, x, y);
ll tmp = y;
y = x - (a / b) * y;
x = tmp;
//x가 양수여야 하면
if (x <= 0) {
x += b;
y -= a;
}
return ret;
}
#include <bits/extc++.h>
//#include "Alice.h"
//#include "Bob.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
using namespace __gnu_pbds;
template<class T> using PBDS = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using multiPBDS = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll gcd(ll a, ll b)
{
if(a==0) return b;
if(b==0) return a;
return gcd(b, a%b);
}
ll minv(ll a, ll b)
{
if(a==0 && b==1) return 0;
if(a==1) return 1;
return b - minv(b%a, a) * b / a;
}
// x == A.first (mod A.second)
// x == B.first (mod B.second)
// returns solution as X == ans.first (mod ans.second)
// if no solution, returns (-1, -1)
// always a good idea to keep 0 <= ?.first < ?.second (for ? : A, B, ans)
pair<ll, ll> solve(pair<ll, ll> A, pair<ll, ll> B)
{
if(A.second == -1 || B.second == -1) return make_pair(-1, -1);
if(A.second == 1) return B;
if(B.second == 1) return A;
ll g = gcd(A.second, B.second); // gcd
ll l = A.second * (B.second / g); // lcm
if((B.first-A.first)%g!=0) return make_pair(-1, -1); // no solution case
ll a = A.second / g;
ll b = B.second / g;
ll mul = (B.first-A.first) / g;
mul = (mul * minv(a%b, b)) % b; // this is now t
ll ret = (mul * A.second + A.first); // n_1 t + a_1
ret %= l; ret = (ret + l) % l; // take modulos
return make_pair(ret, l);
}
//ax+by=c
//ax+by=gcd(a,b)를 만족하는 x와 y를 s와 t에 저장.
//c가 gcd(a,b)의 배수일 때만 가능 (이게 아니라면 x,y는 존재 안 함)
//gcd(a,b)가 return됨.
//log 시간
ll ex_gcd(ll a, ll b, ll& x, ll& y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll ret = ex_gcd(b, a % b, x, y);
ll tmp = y;
y = x - (a / b) * y;
x = tmp;
//x가 양수여야 하면
if (x <= 0) {
x += b;
y -= a;
}
return ret;
}
ll Bob(vector<pint> edges){
vector<pll> a;
for(auto& [u, v]:edges) {
//v-1로 나눈 나머지가 u-1..
a.push_back({u-1,v-1});
}
pll dap=a[0];
for(ll i=1;i<a.size();i++) {
if(__gcd(dap.second,a[i].second)) {
ll m1=dap.second, m2=a[i].second, k1, k2;
ll g=ex_gcd(m1,m2,k1,k2);
dap={m1*k1+dap.first, m1*m2/__gcd(m1,m2)};
}
else dap=solve(dap,a[i]);
if(dap.second>1e18) return dap.first;
}
return dap.first;
}
Compilation message
Bob.cpp: In function 'll Bob(std::vector<std::pair<int, int> >)':
Bob.cpp:83:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(ll i=1;i<a.size();i++) {
| ~^~~~~~~~~
Bob.cpp:86:16: warning: unused variable 'g' [-Wunused-variable]
86 | ll g=ex_gcd(m1,m2,k1,k2);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
820 KB |
Incorrect answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
820 KB |
Incorrect answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
820 KB |
Incorrect answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
