結果
問題 | No.2192 平方数の下14桁 |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
#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" );}