QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139793 | #6519. X Equals Y | MaxBlazeResFire | WA | 1ms | 3716kb | C++14 | 2.8kb | 2023-08-14 16:47:29 | 2023-08-14 16:47:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int X,Y,A,B,swa;
inline bool solve2(){
vector<int> factor;
for( int p = 1 ; p * p < X ; p ++ )
if( ( X - Y ) % p == 0 ) factor.emplace_back( p );//cerr << p << "\n";
for( int p : factor ){
int L = max( X / ( p + 1 ) , ( X * p + X - Y ) / ( p * p + p ) );
L = max( L , max( 2 + ( X - Y ) / p , ( p * p + X - Y ) / p ) );
L = max( L , p ); L ++;
int R = min( min( A , X ) , min( B + ( X - Y ) / p , Y + ( X - Y ) / p ) );
R = min( R , X / p );
//cerr << p << " " << L << " " << R << "\n";
if( L <= R ){
int a = ( L + R ) >> 1,b = ( Y - X ) / p + a;
if( swa ) swap( a , b );
//cerr << "there" << "\n";
printf("YES\n%lld %lld\n",a,b);
return 1;
}
}
return 0;
}
struct sequence{
int Len,Rtag;
vector<int> seq;
sequence( int p = 0 ){ Rtag = p,seq = vector<int>(1),Len = 0; }
inline void prt(){
cerr << Len << " " << Rtag << "\n";
for( int ele : seq ) cerr << ele << " "; cerr << "\n";
}
};
inline bool cmp( sequence A , sequence B ){
if( A.Len != B.Len ) return A.Len < B.Len;
for( int i = 1 ; i <= A.Len ; i ++ )
if( A.seq[i] != B.seq[i] ) return A.seq[i] < B.seq[i];
return 0;
}
inline bool judge( sequence A , sequence B ){
if( A.Len != B.Len ) return 0;
for( int i = 1 ; i <= A.Len ; i ++ )
if( A.seq[i] != B.seq[i] ) return 0;
return 1;
}
vector<sequence> Sa,Sb;
inline bool solve3(){
int lenA = 0,lenB = 0;
Sa.clear(),Sb.clear();
Sa.emplace_back( sequence() ),Sb.emplace_back( sequence() );
for( int a = 2 ; a <= A && a * a <= X ; a ++ ){
Sa.emplace_back( sequence( a ) ),lenA ++;
int tmp = X;
while( tmp ) Sa[lenA].Len ++,Sa[lenA].seq.emplace_back( tmp % a ),tmp /= a;
}
for( int b = 2 ; b <= B && b * b <= Y ; b ++ ){
Sb.emplace_back( sequence( b ) ),lenB ++;
int tmp = Y;
while( tmp ) Sb[lenB].Len ++,Sb[lenB].seq.emplace_back( tmp % b ),tmp /= b;
}
//sort( Sa.begin() , Sa.end() , cmp );
//sort( Sb.begin() , Sb.end() , cmp );
//for( sequence A : Sa ) A.prt();
//for( sequence B : Sb ) B.prt();
int ptb = 1;
for( int pta = 1 ; pta <= lenA ; pta ++ ){
while( ptb <= lenB && cmp( Sb[ptb] , Sa[pta] ) ) ptb ++;
if( ptb > lenB ) return 0;
if( judge( Sa[pta] , Sb[ptb] ) ){
int Ansa = Sa[pta].Rtag,Ansb = Sb[ptb].Rtag;
if( swa ) swap( Ansa , Ansb );
printf("YES\n%lld %lld\n",Ansa,Ansb);
return 1;
}
}
return 0;
}
inline void solve(){
scanf("%lld%lld%lld%lld",&X,&Y,&A,&B);
if( X == Y ){ printf("YES\n2 2\n"); return; }
if( X < Y ) swap( X , Y ),swap( A , B ),swa = 1; else swa = 0;
if( !solve2() ){ if( !solve3() ) printf("NO\n"); }
}
signed main(){
int testcase; scanf("%lld",&testcase);
while( testcase -- ) solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3716kb
input:
6 1 1 1000 1000 1 2 1000 1000 3 11 1000 1000 157 291 5 6 157 291 3 6 10126 114514 789 12345
output:
YES 2 2 NO YES 3 11 NO NO YES 784 9483
result:
wrong answer you didn't find a solution but jury did (test case 4)