#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define double long double #define int long long #define rep(s,i,n) for(int i=s;i>n; #define sc(s) string s;cin>>s; #define dc(d) double d;cin>>d; #define mod 998244353 #define inf 1000000000000000007 #define f first #define s second #define mini(c,a,b) *min_element(c+a,c+b) #define maxi(c,a,b) *max_element(c+a,c+b) #define pi 3.141592653589793238462643383279 #define e_ 2.718281828459045235360287471352 #define P pair #define upp(a,n,x) upper_bound(a,a+n,x)-a; #define low(a,n,x) lower_bound(a,a+n,x)-a; #define pb push_back //printf("%.12Lf\n",); int keta(int x) { rep(0, i, 30) { if (x < 10) { return i + 1; } x = x / 10; } } int gcd(int x, int y) { if (x == 0 || y == 0)return x + y; int aa = x, bb = y; rep(0, i, 1000) { aa = aa % bb; if (aa == 0) { return bb; } bb = bb % aa; if (bb == 0) { return aa; } } } int lcm(int x, int y) { int aa = x, bb = y; rep(0, i, 1000) { aa = aa % bb; if (aa == 0) { return x / bb * y; } bb = bb % aa; if (bb == 0) { return x / aa * y; } } } int integer(double d){ return long(d); } int distance(double a,double b,double c,double d){ return sqrt((b-a)*(b-a)+(c-d)*(c-d)); } bool prime(int x) { if (x == 1)return false; rep(2, i, sqrt(x) + 1) { if (x % i == 0 && x != i) { return false; } } return true; } int max(int a, int b) { if (a >= b)return a; else return b; } string maxst(string s, string t) { int n = s.size(); int m = t.size(); if (n > m)return s; else if (n < m)return t; else { rep(0, i, n) { if (s[i] > t[i])return s; if (s[i] < t[i])return t; } return s; } } int min(int a, int b) { if (a >= b)return b; else return a; } string string_reverse(string s){ int n=s.size(); string t; rep(0,i,n)t+=s[n-i-1]; return t; } int newcom(int n,int y){ int bunsi = 1, bunbo = 1; rep(0, i, y){ bunsi = (bunsi * (n - i)) ; bunbo = (bunbo * (i + 1)) ; int k=gcd(bunsi,bunbo); bunsi/=k; bunbo/=k; } return bunsi/bunbo; } int yakuwa(int n) { int sum = 0; rep(1, i, sqrt(n + 1)) { if (n % i == 0)sum += i + n / i; if (i * i == n)sum -= i; } return sum; } int poow(int n,int m){ int pro=1; int nn=n; while(m){ if(m%2==1)pro=pro*nn%mod; m=m/2; nn=nn*nn%mod; } return pro; } int inv(int n,int m){ int t=poow(m,mod-2)%mod; return n*t%mod; } int com(int n,int m){ int bunsi=1,bunbo=1; for(int i=n-m+1;i<=n;i++)bunsi=bunsi*i%mod; for(int i=1;i<=m;i++)bunbo=bunbo*i%mod; return inv(bunsi,bunbo); } int minpow(int x, int y) { int sum = 1; rep(0, i, y)sum *= x; return sum; } int ketawa(int x, int sinsuu) { int sum = 0; rep(0, i, 100)sum += (x % minpow(sinsuu, i + 1)) / (minpow(sinsuu, i)); return sum; } int sankaku(int a) { if(a%2==0) return a /2*(a+1); else return (a+1)/2*a; } int sames(int a[1111111], int n) { int ans = 0; rep(0, i, n) { if (a[i] == a[i + 1]) { int j = i; while (a[j + 1] == a[i] && j <= n - 2)j++; ans += sankaku(j - i); i = j; } } return ans; } using Graph = vector>; int oya[214514]; int depth[214514]; void dfs(const Graph& G, int v, int p, int d) { depth[v] = d; oya[v] = p; for (auto nv : G[v]) { if (nv == p) continue; // nv が親 p だったらダメ dfs(G, nv, v, d + 1); // d を 1 増やして子ノードへ } } struct UnionFind { vector par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2 UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化 for (int i = 0; i < N; i++) par[i] = i; } int root(int x) { // データxが属する木の根を再帰で得る:root(x) = {xの木の根} if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(int x, int y) { // xとyの木を併合 int rx = root(x); //xの根をrx int ry = root(y); //yの根をry if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける } bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す int rx = root(x); int ry = root(y); return rx == ry; } }; template struct RMQ { const T INF = numeric_limits::max(); int n; vector dat, lazy; RMQ(int n_) : n(), dat(n_ * 4, INF), lazy(n_ * 4, INF) { int x = 1; while (n_ > x) x *= 2; n = x; } /* lazy eval */ void eval(int k) { if (lazy[k] == INF) return; // 更新するものが無ければ終了 if (k < n - 1) { // 葉でなければ子に伝搬 lazy[k * 2 + 1] = min(dat[k],lazy[k]); lazy[k * 2 + 2] = min(dat[k],lazy[k]); } // 自身を更新 dat[k] = min(dat[k],lazy[k]); lazy[k] = INF; } void update(int a, int b, T x, int k, int l, int r) { eval(k); if (a <= l && r <= b) { // 完全に内側の時 lazy[k] = x; eval(k); } else if (a < r && l < b) { // 一部区間が被る時 update(a, b, x, k * 2 + 1, l, (l + r) / 2); // 左の子 update(a, b, x, k * 2 + 2, (l + r) / 2, r); // 右の子 dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); } } void update(int a, int b, T x) { update(a, b, x, 0, 0, n); } T query_sub(int a, int b, int k, int l, int r) { eval(k); if (r <= a || b <= l) { // 完全に外側の時 return INF; } else if (a <= l && r <= b) { // 完全に内側の時 return dat[k]; } else { // 一部区間が被る時 T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2); T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } } T query(int a, int b) { return query_sub(a, b, 0, 0, n); } /* debug */ inline T operator[](int a) { return query(a, a + 1); } void print() { for (int i = 0; i < 2 * n - 1; ++i) { cout << (*this)[i]; if (i != n) cout << ","; } cout << endl; } T max_v[1114514], smax_v[1114514]; T sum[1114514], max_c[1114514]; void update_node_max(int k, T x) { sum[k] += (x - max_v[k]) * max_c[k]; max_v[k] = x; } void push(int k) { if(max_v[k] < max_v[2*k+1]) { update_node_max(2*k+1, max_v[k]); } if(max_v[k] < max_v[2*k+2]) { update_node_max(2*k+2, max_v[k]); } } void update(int k) { sum[k] = sum[2*k+1] + sum[2*k+2]; if(max_v[2*k+1] < max_v[2*k+2]) { max_v[k] = max_v[2*k+2]; max_c[k] = max_c[2*k+2]; smax_v[k] = max(max_v[2*k+1], smax_v[2*k+2]); } else if(max_v[2*k+1] > max_v[2*k+2]) { max_v[k] = max_v[2*k+1]; max_c[k] = max_c[2*k+1]; smax_v[k] = max(smax_v[2*k+1], max_v[2*k+2]); } else { max_v[k] = max_v[2*k+1]; max_c[k] = max_c[2*k+1] + max_c[2*k+2]; smax_v[k] = max(smax_v[2*k+1], smax_v[2*k+2]); } } void _update_min(T x, int a, int b, int k, int l, int r) { if(b <= l || r <= a || max_v[k] <= x) { return; } if(a <= l && r <= b && smax_v[k] < x) { update_node_max(k, x); return; } push(k); _update_min(x, a, b, 2*k+1, l, (l+r)/2); _update_min(x, a, b, 2*k+2, (l+r)/2, r); update(k); } T _query_max(int a, int b, int k, int l, int r) { if(b <= l || r <= a) { return 0; } if(a <= l && r <= b) { return max_v[k]; } push(k); T lv = _query_max(a, b, 2*k+1, l, (l+r)/2); T rv = _query_max(a, b, 2*k+2, (l+r)/2, r); return max(lv, rv); } T _query_sum(int a, int b, int k, int l, int r) { if(b <= l || r <= a) { return 0; } if(a <= l && r <= b) { return sum[k]; } push(k); T lv = _query_sum(a, b, 2*k+1, l, (l+r)/2); T rv = _query_sum(a, b, 2*k+2, (l+r)/2, r); return lv + rv; } }; int n,m,k; bool ok(int t){ if(t/n+t/m-t/lcm(n,m)>n>>m>>k; int l=0,r=inf; while(r-l>=0){ int i=(l+r)/2; if(ok(i)&&!ok(i+1)){ c(i+1) return 0; } else if(ok(i))l=i+1; else r=i; } }