Yuki 176 2種類の切手 ( Math, Square Root Decomposition )
先に T ≥ lcm( A, B ) させるように余る lcm( A, B ) * k を最大の整数 k で取る。
すると最悪の場合、T = 1e9, max( A, B ) = min( A, B ) = 1e4.5 となる。
しかしここで max( A, B ) を枚挙しても間に合う。
O( sqrt( T ) )
#include <bits/stdc++.h> using namespace std; typedef long long ll; signed main(){ ll A, B, T; cin >> A >> B >> T; ll lab = 1LL * A * B / __gcd( A, B ); ll r = max( 0LL, T / lab - 1LL ) * lab; T -= r; if( not ( A >= B ) ) swap( A, B ); ll minv = ( ll ) 2e9; for( ll i = 0; i * A <= T + A - 1; ++i ) minv = min( minv, i * A + ( T - i * A + B - 1 ) / B * B ); cout << r + minv << endl; return 0; }