結果

問題 No.2192 平方数の下14桁
ユーザー 👑 p-adicp-adic
提出日時 2022-10-18 11:53:50
言語 C++17
(gcc 13.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" );
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0