QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408451#6519. X Equals Yx17875487211RE 0ms0kbC++142.8kb2024-05-10 12:32:132024-05-10 12:32:14

Judging History

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

  • [2024-05-10 12:32:14]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-05-10 12:32:13]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,x,y,A,B,W[100],cntw;
bool flag,YES;
bool num_is_ok(int num,int lim){
	if(num>=2&&num<=lim) return 1;
	return 0;
}
bool check_w0(int a,int b,int w1){
	if(x-a*w1!=y-b*w1) return 0;
	int w0=x-a*w1;
	if(w1<0||w1>=min(a,b)) return 0;
	if(w0<0||w0>=min(a,b)) return 0;
	if(a*w1+w0==x&&b*w1+w0==y&&num_is_ok(a,A)&&num_is_ok(b,B)){
		if(flag) swap(a,b);
		printf("YES\n%lld %lld\n",a,b),YES=1;
		return 1;
	}
	return 0;
}
bool cal(int w1){
	int a=x/w1,b=y/w1;
	vector<int> proa,prob;
	for(int i=0;i<=10;i++)
		proa.push_back(a-i),proa.push_back(a+i),
		prob.push_back(b-i),prob.push_back(b+i);
	for(auto pa:proa)
		for(auto pb:prob)
			if(check_w0(pa,pb,w1)) return 1;
	return 0;
}
void DI(int Num,int bas){
	cntw=0;
	while(Num){
		W[++cntw]=Num%bas;
		Num/=bas;
	}
}
int num_base_onb(int di){
	int sum=0,mi=1;
	int tmp=y;
    for(int i=1;i<=cntw;i++){
		sum+=W[i]*mi;
        if(W[i]>=di) return -1;
		mi*=di;
        tmp/=di;
	}
    if(tmp) return -1;
	return sum;
}
int bin_seab(){
	int l=2,r=B;
	while(l<=r){
		int mid=(l+r)>>1;
		int NUM_BASE_ON=num_base_onb(mid);
		if(NUM_BASE_ON==y) return mid; 
		else if(NUM_BASE_ON<y) l=mid+1;
		else r=mid-1;
	} 
	return -1;
}
bool work_on_less_than_sqrta(int a){
	DI(x,a);
	int b=bin_seab();
	if(b!=-1){
		if(flag) swap(a,b);
		printf("YES\n%lld %lld\n",a,b),YES=1;
		return 1;
	}
	return 0;
}
int num_base_ona(int di){
	int sum=0,mi=1;
	int tmp=x;
    for(int i=1;i<=cntw;i++){
		sum+=W[i]*mi;
        if(W[i]>=di) return -1;
		mi*=di;
        tmp/=di;
	}
    if(tmp) return -1;
	return sum;
}
int bin_seaa(){
	int l=2,r=B;
	while(l<=r){
		int mid=(l+r)>>1;
		int NUM_BASE_ON=num_base_ona(mid);
		if(NUM_BASE_ON==x) return mid; 
		else if(NUM_BASE_ON<x) l=mid+1;
		else r=mid-1;
	} 
	return -1;
}
bool work_on_less_than_sqrtb(int b){
	DI(y,b);
	int a=bin_seaa();
	if(a!=-1){
		if(flag) swap(a,b);
		printf("YES\n%lld %lld\n",a,b),YES=1;
		return 1;
	}
	return 0;
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		flag=0;
		scanf("%lld%lld%lld%lld",&x,&y,&A,&B);
		if(x<y) swap(x,y),swap(A,B),flag=1;
		YES=0;
		for(int i=1;i*i<=(x-y);i++)
			if((x-y)%i==0){
				if(cal((x-y)/i+1)) break;
				if(cal(i+1)) break;
				if(cal((x-y)/i-1)) break;
				if(cal(i-1)) break;
				if(cal((x-y)/i)) break;
				if(cal(i)) break;
			}
		if(!YES)
			for(int a=2;a<=A&&a*a<=x;a++)
				if(work_on_less_than_sqrta(a)) break;
		if(!YES) 
			for(int b=2;b<=B&&b*b<=y;b++)
				if(work_on_less_than_sqrtb(b)) break;
		if(!YES&&x==y&&A>=x&&B>=y){
			if(x==1) printf("YES\n%lld %lld\n",x+1,x+1),YES=1;
			else if(num_is_ok(x,A)&&num_is_ok(y,B)) printf("YES\n%lld %lld\n",x,x),YES=1;
		}
		if(!YES) printf("NO\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

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:


result: