Wa #6 #8 #10 #15 80pts 求hack(悬关)
  • 板块P1852 跳跳棋
  • 楼主CAICAIA
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/19 15:58
  • 上次更新2024/8/19 17:57:02
查看原帖
Wa #6 #8 #10 #15 80pts 求hack(悬关)
704655
CAICAIA楼主2024/8/19 15:58
#include<bits/stdc++.h>
using namespace std;
const long long MX=35,INF=1000010000;
struct Node{
    long long beg,a,b;
    const bool operator==(const Node &x){
        return beg==x.beg&&a==x.a&&b==x.b;
    }
};
Node gcd(Node x,long long k){
    // printf("be=%lld a=%lld b=%lld k=%lld\n",x.beg,x.a,x.b,k);
    if(x.a==x.b)  return x;
    if(x.a==1)  return (Node){x.beg+min(k,x.b-1),1,max(1ll,x.b-k)};
    if(x.b==1)  return (Node){x.beg,max(1ll,x.a-k),1};
    if(x.a>x.b){
        if(x.b*k<x.a)  return (Node){x.beg,x.a-x.b*k,x.b};
        return gcd((Node){x.beg,x.a%x.b,x.b},k-x.a/x.b);
    }
    else{
        if(x.a*k<x.b)  return (Node){x.beg+k*x.a,x.a,x.b-x.a*k};
        return gcd((Node){x.beg+(x.b/x.a)*x.a,x.a,x.b%x.a},k-x.b/x.a);
    }
}
long long high(Node x){
    long long l=0,r=INF,mid,ans=0;
    while(l<=r){
        mid=(l+r)>>1;
        Node now=gcd(x,mid);
        if(now.a==now.b)ans=mid,r=mid-1;
        else  l=mid+1;
    }
    return ans;
}
int xx[3]={0};
inline Node toN(int a,int b,int c){
    xx[0]=a,xx[1]=b,xx[2]=c;sort(xx,xx+3);
    Node x;x.beg=xx[0],x.a=xx[1]-xx[0],x.b=xx[2]-xx[1];
    return x;
}
signed main(){
    Node x,y;long long a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);x=toN(a,b,c);
    scanf("%lld%lld%lld",&a,&b,&c);y=toN(a,b,c);
    if(!(gcd(x,INF)==gcd(y,INF)))  return puts("NO"),0;
    // printf("NO");return 0;
    long long high_x=high(x),high_y=high(y);

    // high_x=0;
    // high_y=high_y/high_x;
    // printf("%d %d\n",high_x,high_y);
    if(high_x<high_y)  swap(high_x,high_y),swap(x,y);
    long long sum=high_x-high_y;x=gcd(x,sum);

    long long l=0,r=INF,mid,ans=0;
    while(l<=r){
        mid=(l+r)>>1;
        Node xi=gcd(x,mid),yi=gcd(y,mid);
        if(xi==yi)ans=mid,r=mid-1;
        else  l=mid+1;
    }sum+=ans*2;
    printf("YES\n%lld",sum);
    return 0;
}



// signed main(){
//     long long T;scanf("%lld",&T);
//     while(T--){
//         long long x,y,z,k;
//         scanf("%lld%lld%lld%lld",&x,&y,&z,&k);
//         Node node;
//         node.a=y-x,node.b=z-y,node.beg=x;
//         node=gcd(node,k);
//         printf("beg=%lld a=%lld b=%lld\n",node.beg,node.a,node.b);
//         printf("x=  %lld y=%lld z=%lld\n\n",node.beg,node.beg+node.a,node.beg+node.a+node.b);
//     }
//     return 0;
// }
/*
5 9 NO
6 pan cuo
4
1 2 8 146786
1 2 8 1
3 9 10 344
3 9 10 3
*/
2024/8/19 15:58
加载中...