QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139788 | #6519. X Equals Y | MaxBlazeResFire | TL | 470ms | 8348kb | C++14 | 2.7kb | 2023-08-14 16:36:35 | 2023-08-14 16:36:38 |
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: 100
Accepted
time: 1ms
memory: 3792kb
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 YES 4 5 NO YES 784 9483
result:
ok correct (6 test cases)
Test #2:
score: 0
Accepted
time: 6ms
memory: 3708kb
input:
1000 920 661 756 534 52 454 31 218 980 77 812 6 729 733 289 660 161 643 21 475 602 525 329 274 782 167 279 113 875 100 388 16 426 498 341 417 433 751 312 39 91 50 47 39 941 388 247 46 725 808 148 486 945 405 700 145 647 509 152 445 45 564 16 468 843 40 530 3 722 36 323 22 568 472 443 41 38 749 25 42...
output:
YES 673 414 YES 15 149 NO YES 266 268 NO YES 81 70 YES 253 48 NO YES 277 349 NO NO NO NO YES 410 140 YES 101 78 YES 13 186 NO NO YES 46 38 YES 11 248 NO NO YES 194 18 YES 141 110 NO YES 725 321 NO YES 56 185 NO YES 65 28 NO NO YES 91 51 YES 6 5 NO NO NO NO NO YES 303 108 NO YES 203 190 YES 178 378 Y...
result:
ok correct (1000 test cases)
Test #3:
score: 0
Accepted
time: 115ms
memory: 3896kb
input:
1000 312788 308299 292039 230765 263760 329714 198045 86472 945524 951268 792172 748100 922790 262573 363596 34883 755556 714487 234743 610394 413603 489527 114329 351936 409240 356171 378350 234973 300813 97383 263307 49846 579258 900270 84403 704902 563965 876076 387516 770189 36896 156893 23161 1...
output:
YES 196946 192457 YES 35325 44747 YES 607559 613303 NO YES 101557 95690 YES 108865 134173 YES 259598 206529 YES 252699 49269 YES 83577 137079 YES 334749 646860 YES 20805 140802 YES 38694 37780 YES 15781 32158 YES 338300 126029 YES 102486 98948 YES 1370 9013 NO YES 499593 149079 YES 132367 86618 YES ...
result:
ok correct (1000 test cases)
Test #4:
score: 0
Accepted
time: 470ms
memory: 8348kb
input:
1000 981241785 906230829 601363803 626653490 197057696 698550046 128696358 449956015 182548925 796382933 101642956 339324198 816288818 177783961 308532802 32376477 628394197 777548138 355072973 757299936 599075146 752655475 473746059 323396924 261214299 95047810 181049121 60329182 7484303 329571035 ...
output:
YES 564745087 489734131 YES 82107373 332853548 YES 53243436 257854772 YES 146891 31990 YES 334635036 483788977 YES 174730251 225923694 NO YES 1930275 109292519 YES 1785159 1757162 YES 251509367 279658449 NO YES 8143209 7797898 YES 21569219 181104747 YES 5800085 6032056 YES 75498800 123065721 YES 115...
result:
ok correct (1000 test cases)
Test #5:
score: 0
Accepted
time: 157ms
memory: 4020kb
input:
1000 11131470 5473008 893 586 160457243 377399003 195 363 33293118 10204988 348 650 76153236 165484206 788 591 363322142 108960566 994 862 10849 1346589 861 662 425071 7754389 221 245 5472186 246060285 479 804 699145 16995055 56 861 215170 3080970 423 722 355522 9691597 211 923 24159424 15965332 579...
output:
YES 36 30 YES 50 62 YES 50 37 NO NO YES 16 86 YES 28 74 YES 10 19 NO YES 33 83 YES 16 37 YES 93 81 YES 70 80 NO YES 50 56 YES 99 29 YES 47 33 YES 2 2 YES 14 77 YES 89 84 YES 42 7 YES 48 93 YES 48 22 YES 63 48 YES 73 96 NO YES 21 20 YES 36 55 YES 68 24 YES 11 89 YES 36 64 YES 13 34 YES 57 59 YES 65 6...
result:
ok correct (1000 test cases)
Test #6:
score: -100
Time Limit Exceeded
input:
1000 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 99490...