#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; /** * Dijkstra法により最短距離を求める * * template引数のint Vは頂点数 */ template struct Dijkstra { typedef int T; /// 辺の距離の型 const int INF = 1e9; typedef pair P; vector

g[V]; /// 辺のクリア void init() { for (int i = 0; i < V; i++) { g[i].clear(); } } /// 辺の追加 void add(int from, int to, T dist) { g[from].push_back(P(dist, to)); } T res[V]; /// execを行うと、これに最短距離が入る void exec(int s) { fill_n(res, V, INF); priority_queue, greater

> q; q.push(P(0, s)); res[s] = 0; while (!q.empty()) { P p = q.top(); q.pop(); if (res[p.second] < p.first) continue; for (P e: g[p.second]) { if (p.first+e.first < res[e.second]) { res[e.second] = p.first+e.first; q.push(P(e.first+p.first, e.second)); } } } return; } }; Dijkstra<200000> djk; int main() { ll res = 1LL<<55; ll a, b, t; cin >> a >> b >> t; if (b < 100000) { for (int i = 0; i < b; i++) { djk.add(i, (i+a)%b, 1); } djk.exec(0); for (int i = 0; i < b; i++) { ll aa = a*djk.res[i]; res = min(res, max(0LL, (t-aa+b-1)/b)*b+aa); } } else { for (int i = 0; i < 100000; i++) { ll bb = b*i; res = min(res, max(0LL, (t-bb+a-1)/a)*a+bb); } } cout << res << endl; return 0; }