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

提出ソース

結果

問題	No.2066 Simple Math !
ユーザー	👑 p-adic
提出日時	2022-09-17 22:44:47
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	4,517 bytes
コンパイル時間	2,169 ms
コンパイル使用メモリ	208,240 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-06-01 15:19:35
合計ジャッジ時間	7,256 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	5 ms 6,812 KB
testcase_02	RE	-
testcase_03	AC	6 ms 6,940 KB
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	AC	7 ms 6,944 KB
testcase_31	AC	6 ms 6,940 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 = r * Q;
      } else {
	ll x_a_sq_a = ( K * Q ) / P;
	ll x_a_sq;
	ll x_a = 0;
	ll power = power_max;
	while( power != 0 ){
	  ll x_a_p = x_a + power;
	  x_a_sq = ( x_a_p * ( x_a_p + 1 ) ) / 2;
	  ll difference = x_a_sq_a - x_a_sq;
	  if( difference >= 0 ){
	    x_a = x_a_p;
	    if( difference == 0 ){
	      break;
	    }
	  }
	  power /= 2;
	}
	assert( x_a > 0 );
	answer = ( K * Q - P * x_a_sq ) / x_a;
	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;
	  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;
	    }
	    answer += power;
	  } else {
	    answer_c = answer - power;
	    n = answer_c / P + 1;
	    floor_sum = FloorSum( answer_c % P , P , Q , n ) + n - 1;
	    while( K < floor_sum ){
	      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;
	    }
	  }
	  while( K != floor_sum ){
	    power /= 2;
	    assert( power != 0 );
	    answer += power;
	    n = answer / P + 1;
	    floor_sum = FloorSum( answer % P , P , Q , n ) + n - 1;
	  }
	}
      }
    }
    answer *= gcd;
    cout << answer << "\n";
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード