QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408451 | #6519. X Equals Y | x17875487211 | RE | 0ms | 0kb | C++14 | 2.8kb | 2024-05-10 12:32:13 | 2024-05-10 12:32:14 |
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