結果

問題 No.2192 平方数の下１４桁
ユーザー 👑 p-adicp-adic
提出日時 2022-10-18 11:53:50
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 109 ms / 2,000 ms
コード長 2,522 bytes
コンパイル時間 749 ms
コンパイル使用メモリ 70,012 KB
実行使用メモリ 4,356 KB
最終ジャッジ日時 2023-10-14 08:32:08
合計ジャッジ時間 4,628 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 1 ms
4,352 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 1 ms
4,352 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 1 ms
4,348 KB
testcase_09 AC 1 ms
4,348 KB
testcase_10 AC 2 ms
4,352 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,352 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 2 ms
4,348 KB
testcase_17 AC 4 ms
4,352 KB
testcase_18 AC 5 ms
4,352 KB
testcase_19 AC 51 ms
4,352 KB
testcase_20 AC 84 ms
4,352 KB
testcase_21 AC 91 ms
4,348 KB
testcase_22 AC 106 ms
4,352 KB
testcase_23 AC 54 ms
4,348 KB
testcase_24 AC 108 ms
4,352 KB
testcase_25 AC 106 ms
4,352 KB
testcase_26 AC 109 ms
4,352 KB
testcase_27 AC 2 ms
4,352 KB
testcase_28 AC 2 ms
4,348 KB
testcase_29 AC 2 ms
4,352 KB
testcase_30 AC 2 ms
4,352 KB
testcase_31 AC 1 ms
4,352 KB
testcase_32 AC 2 ms
4,348 KB
testcase_33 AC 2 ms
4,348 KB
testcase_34 AC 2 ms
4,348 KB
testcase_35 AC 2 ms
4,348 KB
testcase_36 AC 1 ms
4,348 KB
testcase_37 AC 1 ms
4,356 KB
testcase_38 AC 2 ms
4,352 KB
testcase_39 AC 2 ms
4,352 KB
testcase_40 AC 55 ms
4,348 KB
testcase_41 AC 55 ms
4,348 KB
testcase_42 AC 89 ms
4,352 KB
testcase_43 AC 55 ms
4,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;

#define CIN( LL , A ) LL A; cin >> A 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0 
#define MIN( A , B ) A < B ? A : B;


// 以下、自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。
template <typename INT>
INT QuadraticResidue( const INT& a , const INT& p );

template <typename INT>
INT QuadraticResidue( const INT& a , const INT& p )
{

  INT r = a % p;

  if( r == 0 ){

    return 0;

  }

  INT q = 2;
  INT e = 0;
  INT count = 0;

  while( r % q == 0 ){

    r /= q;
    e++;

  }

  if( e % 2 == 1 ){

    if( ( ( p * p - 1 ) / 8 )% 2 == 1 ){

      count++;
      
    }

  }

  q++;
  
  while( r != 1 ){

    if( r % q == 0 ){

      e = 0;
      
      while( r % q == 0 ){

	r /= q;
	e++;

      }

      if( e % 2 == 1 ){

	INT qr = QuadraticResidue<INT>( p , q ) * ( ( ( ( p - 1 ) * ( q - 1 ) ) / 4 ) % 2== 0 ? 1 : -1 );

	if( qr == -1 ){

	  count++;
	  
	}
	
      }

    }

    q += 2;

    if( q * q > r ){

      q = r;
      
    }

  }

  return count % 2 == 0 ? 1 : -1;
  
}


#define PF					\
  if( B % p == 0 ){				\
    pfB[K] = p;					\
    ll& peBp = peB[K];				\
    K++;					\
    while( B % p == 0 ){			\
      B /= p;					\
      peBp++;					\
    }						\
  }						\
						\


#include <cassert>

int main()
{
  CIN( ll , B );
  assert( 2 <= B && B <= 100000000000000 );
  CIN( ll , R );
  assert( 0 <= R && R < B );
  ll pfB[60];
  ll peB[60] = {};
  ll K = 0;
  ll p = 2;
  {
    PF;
    p++;
  }
  while( B != 1 ){
    PF;
    p += 2;
    if( p * p > B ){
      p = B;
    }
  }
  ll peR[60] = {};
  ll c[60];
  FOR( k , 0 , K ){
    ll& ck = c[k];
    ck = R;
    ll& pfBk = pfB[k];
    ll& peBk = peB[k];
    ll& peRk = peR[k];
    while( ck % pfBk == 0 && peRk < peBk ){
      ck /= pfBk;
      peRk++;
    }
    if( peRk < peBk && peRk % 2 == 1 ){
      RETURN( "NO" );
    }
  }
  ll k_start = 0;
  if( pfB[0] == 2 ){
    ll& peB0 = peB[0];
    if( peR[0] < peB0 ){
      ll E = MIN( peB0 , 3 );
      ll b = 1;
      FOR( e , 0 , E ){
	b *= 2;
      }
      if( c[0] % b != 1 ){
	RETURN( "NO" );
      }
    }
    k_start++;
  }
  FOR( k , k_start , K ){
    if( QuadraticResidue<ll>( c[k] , pfB[k] ) == -1 ){
      RETURN( "NO" );
    }
  }
  RETURN( "YES" );
}
0