Yuki 176 2種類の切手 ( Math, Square Root Decomposition )

No.176 2種類の切手 - yukicoder

先に 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;
}