結果

問題 No.2066 Simple Math !
コンテスト
ユーザー 👑 p-adic
提出日時 2022-09-18 00:11:40
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,247 bytes
コンパイル時間 2,248 ms
コンパイル使用メモリ 202,216 KB
最終ジャッジ日時 2025-02-07 11:30:02
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG 
#include<bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using ll = long long;

#define CIN( LL , A ) LL A; cin >> A 
#define GETLINE( A ) string A; getline( cin , A ) 
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) 
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT 
#define MIN( A , B ) A < B ? A : B;
#define MAX( A , B ) A < B ? B : A;

template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; }

// 以下、自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。


template <typename INT>
inline INT GCD( const INT& a , const INT& b )
{
  INT a_c = a >= 0 ? a : -a;
  INT b_c = b >= 0 ? b : -b;
  while( a_c > 0 && b_c > 0 ){
    if( a_c < b_c ){
      b_c -= a_c * ( b_c / a_c );
    } else {
      a_c -= b_c * ( a_c / b_c );
    }
  }
  return a_c > 0 ? a_c : b_c;
}

template <typename INT>
inline INT FloorSum( const INT& a_0 , const INT& a_1 , const INT& q , const INT& n )
{

  if( n == 0 ){

    return 0;
    
  } else if( n == 1 ){

    return a_0 / q;

  }
  
  const INT r_0 = a_0 % q;
  const INT r_1 = a_1 % q;
  const INT value_lim = ( r_0 + r_1 * n ) / q;
  INT answer = ( a_0 / q ) * n + ( a_1 / q ) * ( n % 2 == 0 ? ( n / 2 ) * ( n - 1 ) : n * ( ( n - 1 ) / 2 ) );
  
  if( value_lim != 0 ){

    const INT r_1_n_approx = value_lim * q - r_0;
    const INT e = r_1_n_approx % r_1;
    // r_1 == 0と仮定するとvalue_lim == r_0 / qすなわちvalue_lim == 0となり矛盾する。
    answer += ( n - ( ( r_1_n_approx + ( r_1 - 1 ) ) / r_1 ) ) * value_lim + FloorSum( e == 0 ? 0 : r_1 - e , q , r_1 , value_lim );
    
  }
  
  return answer;
  
}

int main()
{
  UNTIE;
  CIN( ll , T );
  ll P , Q , K;
  ll gcd;
  constexpr const ll power_max = ll( 1 ) << 31;
  REPEAT( T ){
    cin >> P >> Q >> K;
    assert( P > 0 && Q > 0 && K > 0 );
    gcd = GCD( P , Q );
    P /= gcd;
    Q /= gcd;
    ll K_border = ( ( P - 1 ) * ( Q - 1 ) ) / 2;
    ll answer;
    if( K > K_border ){
      answer = K + K_border;
    } else {
      if( P < Q ){
	swap( P , Q );
      }
      ll r = P / Q;
      if( K <= r ){
	answer = r * Q;
      } else {
	ll K_a;
	ll x_a = 0;
	ll power = power_max;
	ll x_a_p = 0;
	ll difference;
	while( power != 0 ){
	  x_a_p = x_a + power;
	  K_a = ( P * ( x_a_p * ( x_a_p + 1 ) ) / 2 ) / Q + x_a_p - 1;
	  difference = K - K_a;
	  if( difference >= 0 ){
	    x_a = x_a_p;
	    if( difference == 0 ){
	      break;
	    }
	  }
	  power /= 2;
	}
	assert( x_a > 0 );
	answer = ( Q * ( K - x_a + 1 ) - P * ( ( x_a * ( x_a + 1 ) ) / 2 ) ) / x_a;
	if( answer < 1 ){
	  answer = 1;
	}
	ll n = answer / P + 1;
	ll floor_sum = FloorSum( answer % P , P , Q , n ) + n - 1;
	if( K != floor_sum ){
	  ll answer_c = answer;
	  power = 1;
	  bool match = false;
	  if( K > floor_sum ){
	    answer_c = answer + power;
	    n = answer_c / P + 1;
	    ll floor_sum_prev = floor_sum;
	    floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1;
	    while( K > floor_sum ){
	      power *= 2;
	      answer_c = answer + power;
	      n = answer_c / P + 1;
	      floor_sum_prev = floor_sum;
	      floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1;
	    }
	    if( K != floor_sum ){
	      power /= 2;
	      floor_sum = floor_sum_prev;
	    }
	  } else {
	    answer_c = answer - power;
	    n = answer_c / P + 1;
	    floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1;
	    while( true ){
	      power *= 2;
	      answer_c = answer - power;
	      if( answer_c <= 0 ){
		answer_c = 1;
		n = answer_c / P + 1;
		floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1;
		break;
	      }
	      n = answer_c / P + 1;
	      floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1;
	      if( K > floor_sum ){
		power /= 2;
		answer = answer_c;
		break;
	      } else if( K == floor_sum ){
		answer_c--;
		n = answer_c / P + 1;
		if( K != FloorSum( answer_c % P , P , Q , n ) + n - 1 ){
		  match = true;
		  power /= 2;
		  answer = answer_c + 1;
		  break;
		}
	      }
	    }
	  }
	  if( ! match ){
	    while( true ){
	      assert( power != 0 );
	      answer_c = answer + power;
	      n = answer_c / P + 1;
	      floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1;
	      if( K > floor_sum ){
		answer = answer_c;
	      } else if( K == floor_sum ){
		if( answer_c == 1 || power == 1 ){
		  answer = answer_c;
		  break;
		} else {
		  answer_c--;
		  n = answer_c / P + 1;
		  if( K > FloorSum( answer_c % P , P , Q , n ) + n - 1 ){
		    answer = answer_c + 1;
		    break;
		  }
		}
	      }
	      power /= 2;
	    }
	  }
	}
      }
    }
    answer *= gcd;
    cout << answer << "\n";
  }
  return 0;
}
0