QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#139765#6519. X Equals YMaxBlazeResFireWA 2ms3752kbC++141.9kb2023-08-14 15:31:562023-08-14 15:31:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-14 15:31:59]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3752kb
  • [2023-08-14 15:31:56]
  • 提交

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 ) ) + 1;
		L = max( L , 2 + ( X - Y ) / p );
		int R = min( min( A , X ) , min( B + ( X - Y ) / p , Y + ( X - Y ) / p ) );
		R = min( R , X / p );
		if( L <= R ){
			int a = ( L + R ) >> 1,b = ( Y - X ) / p + a;
			if( swa ) swap( a , b );
			printf("YES\n%lld %lld\n",a,b);
			return 1;
		}
	}
	return 0;
}

vector< vector<int> > Fa,Fb;

inline bool solve3(){
	int lenA = 0,lenB = 0;
	Fa.clear(),Fb.clear();
	Fa.emplace_back( vector<int>() ),Fb.emplace_back( vector<int>() );
	for( int a = 2 ; a <= A && a * a <= X ; a ++ ){
		Fa.emplace_back( vector<int>() ),lenA ++;
		int tmp = X;
		while( tmp ) Fa[lenA].emplace_back( tmp % a ),tmp /= a;
	}
	for( int b = 2 ; b <= B && b * b <= Y ; b ++ ){
		Fb.emplace_back( vector<int>() ),lenB ++;
		int tmp = Y;
		while( tmp ) Fb[lenB].emplace_back( tmp % b ),tmp /= b;
	}
	int ptb = 1;
	for( int pta = 1 ; pta <= lenA ; pta ++ ){
		while( ptb <= lenB && Fb[ptb].size() > Fa[pta].size() ) ptb ++;
		if( ptb > lenB ) return 0;
		int LEN = Fa[pta].size(),flg = 0;
		for( int j = 0 ; j < LEN ; j ++ )
			if( Fa[pta][j] != Fb[ptb][j] ){ flg = 1; break; }
		if( !flg ){
			if( swa ) swap( pta , ptb );
			printf("YES\n%lld %lld\n",pta + 1,ptb + 1);
			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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3752kb

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
2 10
YES
4 5
NO
YES
784 9483

result:

ok correct (6 test cases)

Test #2:

score: -100
Wrong Answer
time: 2ms
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
YES
35 4
YES
277 349
NO
NO
NO
NO
YES
410 140
YES
101 78
YES
13 186
NO
YES
103 5
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
YES
57 11
YES
10 39
YES
91 51
YES
6 5
YES
57 10
NO
NO
NO
NO
YES
30...

result:

wrong answer wrong solution, (875 in base 35) != (100 in base 4) (test case 8)