Воскресным утром в кинотеатре в двух залах одновременно начался показ фильмов. Фильм, показываемый в первом зале, имеет длительность a минут, а фильм, показываемый во втором зале — b минут. В каждом из залов после окончания фильма его сразу начинают показывать с начала. Любой посетитель может войти в любой из залов.
Лука знает, что с момента начала показа фильмов прошло t минут. Ему неважно, какой фильм посмотреть, так как Лука просто хочет весело провести время. Однако мальчик нетерпелив, поэтому хочет узнать, через какое минимальное время хотя бы в одном из залов начнут показывать фильм с начала.
Формат входных данных
Первая строка содержит одно целое число a (1≤a≤2⋅109) — длительность первого фильма в минутах.
Вторая строка содержит одно целое число b (1≤b≤2⋅109) — длительность второго фильма в минутах.
Третья строка содержит одно целое число t (0≤t≤2⋅1018) — время в минутах, прошедшее с начала показа фильмов.
Обратите внимание, что входные данные и ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.
Формат выходных данных
Выведите одно целое число — минимальное время в минутах, через которое хотя бы в одном зале начнут показывать фильм с начала.
Система оценки
Решения, правильно работающие только для случаев, когда t не превосходит 2⋅109, будут оцениваться в 60 баллов.
Пояснение
Рассмотрим первый пример из условия. Фильм, показываемый в первом зале, имеет длительность 3 минуты, а фильм, показываемый во втором зале — 7 минут. Таким образом, первый фильм начинается спустя 0,3,6,9,12,… минут после начала показа, а второй фильм — спустя 0,7,14,21,28,… минут после начала показа. Лука знает, что с начала показа фильмов прошло 10 минут. Для того, чтобы попасть на начало первого фильма, ему придётся подождать 12−10=2 минуты, а чтобы попасть на начало второго фильма — 14−10=4 минуты.
Рассмотрим второй пример из условия. Оба фильма имеют длительность 5 минут и начинаются спустя 0,5,10,15,… минут после начала показа. Так как с момента начала показа прошло 10 минут, Луке не придётся ждать.
Рассмотрим третий пример из условия. Оба фильма начнутся спустя 9 минут после начала показа, поэтому вне зависимости от выбора фильма Луке придётся подождать 9−8=1 минуту.
1 Ответ
Ответ:
#include<bits/stdc++.h>
//#pragma GCC optimize(«Ofast»)
//#pragma GCC target(«sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2 «)
using namespace std;
#define all(x) (x).begin(), (x).end()
using ll = long long;
using ld = long double;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e7 + 5;
const int mod = 1e9 + 7;
std::random_device rd;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch() .count());
ll get(ll len, ll t) {
ll l = 0, r = t / len + 5;
while (r — l > 1) {
ll m = (r + l) >> 1;
ll time = len * m;
if (time >= t) {
r = m;
} else {
l = m;
}
}
return abs(t — r * len);
}
void solve() {
ll a, b, t;
cin >> a >> b >> t;
ll first = get(a, t);
ll second = get(b, t);
cout << min(first, second);
}
signed main() {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int tt = 1;
while (tt—) {
solve();
}
return 0;
}