結果

問題 No.2119 一般化百五減算
コンテスト
ユーザー 👑 p-adic
提出日時 2022-10-05 09:45:45
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 2,442 bytes
コンパイル時間 569 ms
コンパイル使用メモリ 68,424 KB
最終ジャッジ日時 2025-02-07 21:54:59
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdint.h>
using namespace std;

using ll = long long;

#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define CIN( LL , A ) LL A; cin >> A 
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 
#define RESIDUE( A , P ) ( A >= 0 ? A % P : P - ( - A - 1 ) % P - 1 )

#include <cassert>

#define MAIN main

void CRT( ll& answer , ll& lcm ,  const ll& B_0 , const ll& C_0 , const ll& B_1 , const ll& C_1 )
{
  ll A[2][2];
  ll B[2] = { B_0 , B_1 };
  int i_0 = ( B_0 >= B_1 ? 0 : 1 );
  int i_1 = 1 - i_0;
  FOR( i , 0 , 2 ){
    ll ( & Ai )[2] = A[i];
    FOR( j , 0 , 2 ){
      Ai[j] = ( i == j ? 1 : 0 );
    }
  }
  ll q;
  while( B[i_1] != 0 ){
    ll& B_i_0 = B[i_0];
    ll& B_i_1 = B[i_1];
    q = B_i_0 / B_i_1;
    ll ( &A_i_0 )[2] = A[i_0];
    ll ( &A_i_1 )[2] = A[i_1];
    A_i_0[i_0] -= q * A_i_1[i_0];
    A_i_0[i_1] -= q * A_i_1[i_1];
    B_i_0 %= B_i_1;
    swap( i_0 , i_1 );
  }
  ll& gcd = B[i_0];
  ll c = C_0 % gcd;
  if( C_1 % gcd != c ){
    answer = -1;
    return;
  }
  lcm = ( B_0 / gcd ) * B_1;
  ll ( &A_i_0 )[2] = A[i_0];
  ll& A_i_00 = A_i_0[0];
  A_i_00 *= ( C_1 - c ) / gcd;
  A_i_00 = RESIDUE( A_i_00 , lcm );
  ll& A_i_01 = A_i_0[1];
  A_i_01 *= ( C_0 - c ) / gcd;
  A_i_01 = RESIDUE( A_i_01 , lcm );
  // answerやlcmが他の変数への参照である場合に書き換えが生じうることに注意
  answer = ( c + A_i_00 * B_0 + A_i_01 * B_1 ) % lcm;
  return;
}

int MAIN()
{
  UNTIE;
  constexpr const ll bound = 1000000;
  CIN( ll , N );
  assert( 0 <= N && N <= bound );
  CIN( int , I );
  assert( 1 <= I && I <= bound );
  ll b = 1;
  ll c = 0;
  int i = 0;
  ll B , C , lcm;
  while( i < I && b <= N ){
    cin >> B >> C;
    assert( 0 <= B && B <= bound );
    assert( -bound <= C && C <= bound );
    C = RESIDUE( C , B );
    CRT( c , lcm , b , c , B , C );
    if( c == -1 || c > N ){
      RETURN( "NaN" );
    }
    b = lcm;
    i++;
  }
  while( i < I ){
    cin >> B >> C;
    assert( 0 <= B && B <= bound );
    assert( -bound <= C && C <= bound );
    C = RESIDUE( C , B );
    if( c % B != C ){
      RETURN( "NaN" );
    }
    i++;
  }
  RETURN( c );
}
0