結果

問題 No.2192 平方数の下１４桁
コンテスト
ユーザー 👑 p-adic
提出日時 2022-10-18 11:53:50
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 104 ms / 2,000 ms
コード長 2,522 bytes
コンパイル時間 712 ms
コンパイル使用メモリ 68,812 KB
最終ジャッジ日時 2025-02-08 08:03:35
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

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