#798762 (C++17) No.2066 Simple Math !

提出ソース

結果

問題	No.2066 Simple Math !
ユーザー	👑 p-adic
提出日時	2022-09-18 01:06:56
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	377 ms / 2,000 ms
コード長	5,304 bytes
コンパイル時間	2,347 ms
コンパイル使用メモリ	211,196 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-01 15:21:48
合計ジャッジ時間	10,850 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	5 ms 5,248 KB
testcase_02	AC	17 ms 5,376 KB
testcase_03	AC	6 ms 5,376 KB
testcase_04	AC	369 ms 5,376 KB
testcase_05	AC	370 ms 5,376 KB
testcase_06	AC	370 ms 5,376 KB
testcase_07	AC	369 ms 5,376 KB
testcase_08	AC	369 ms 5,376 KB
testcase_09	AC	374 ms 5,376 KB
testcase_10	AC	377 ms 5,376 KB
testcase_11	AC	374 ms 5,376 KB
testcase_12	AC	376 ms 5,376 KB
testcase_13	AC	377 ms 5,376 KB
testcase_14	AC	337 ms 5,376 KB
testcase_15	AC	341 ms 5,376 KB
testcase_16	AC	342 ms 5,376 KB
testcase_17	AC	341 ms 5,376 KB
testcase_18	AC	341 ms 5,376 KB
testcase_19	AC	90 ms 5,376 KB
testcase_20	AC	87 ms 5,376 KB
testcase_21	AC	86 ms 5,376 KB
testcase_22	AC	89 ms 5,376 KB
testcase_23	AC	88 ms 5,376 KB
testcase_24	AC	251 ms 5,376 KB
testcase_25	AC	250 ms 5,376 KB
testcase_26	AC	247 ms 5,376 KB
testcase_27	AC	248 ms 5,376 KB
testcase_28	AC	247 ms 5,376 KB
testcase_29	AC	43 ms 5,376 KB
testcase_30	AC	7 ms 5,376 KB
testcase_31	AC	6 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #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 = K * 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;
	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 {
	  if( K == floor_sum ){
	    answer_c = answer - power;
	    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;
	    }
	  }
	  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;
}

yukicoder

結果

テストケース

ソースコード