2026牛客寒假算法基础集训营4 D题 东风谷早苗与博丽灵梦

前置知识 数论裴蜀定理 exgcd 龟速乘（防爆long long

首先我们来观察一下这道题是两个人相遇求最短时间，那么写成方程就是aX+sY=x的问题

这里总路程是x，首先我们肯定是要能够构造出一个解的，根据裴蜀定理，我们可以知道上面的二元一次方程要有整数解的话，x%gcd(a,s)=0，否则就不能构造出来两个整数解，我们先根据这个进行第一步判断同时求出ax0+sy0=exgcd(a,s) 中的x0和y0

那么回过来看问题我们实际上想要求的是aX+sY=x 那么我们对上面的公式变形，记g=exgcd(a,s) ** 即变为 ax0x/g + sy0x/g = x 那么现在x0和y0都不一定都是正整数，我们想要对它进行变形，因为我们想要求最小的变化这样才能找到最精确的整数点**

这里需要最小化步长 对于x来说dx = s/g 为什么呢？因为对于 ax + sy = c来说 a(x+dx) + s(y-dy) = c和原式没区别，而这可以改变X和Y，我们想要最小微调就需要改变最小步长，所以我们后面计算出来的值都要对dx或者dy取模

接下来我们就想要求 aX + sY = x中的X和Y了 X+kdx就是c1 Y-kdy就是c2 这里的X和Y是一组特解其实我们只要求一个就行了，另一个可以通过公式求出来，这里我们求X

那么 X 通过观察上面的公式可以发现就是 x0*x/g 那么这里为了防止爆longlong 使用龟速乘

X = (cheng(x0,x/g,dx)%dx+dx)%dx; 

这里进行负数化最小正整数的取模，因为x0可能是负数

这里又有一个关键判断，如果说最小的X*a都能大于x的话就说明Y只能是负数而这是不对的，所以要特判

现在我们求出了X 接下来就是求Y 那么我们有上面的公式所以直接变形

Y = (x-a*X)/s;

好了我们现在有了X也有了Y 接下来就是另一个问题了 我们想要时间最短怎么办呢，在相遇问题中时间最短取决于两个人所用时间的最大值，也就是我们要求两个最大值的最小值，那我们知道X增大Y必然减小，为了让最大值最小就要让X和Y尽可能靠近，我们不妨假设 X+kdx = Y-kdy 变形就可以得出k = (Y-X)/(dx+dy)

这里是点睛之笔我们不需要通过二分，直接相除就可以得到k，那因为除法向下取整了，所以答案也可能是k+1，我们需要进行判断 这里我们初始化c1 = X+kdx c2 = Y-kdy cc1 = X+(k+1)dx cc2 = Y-(k+1)dy 因为答案必然在k和k+1之间，而k+1可能把c2变成负数所以需要特别判断

如果cc2<0那么直接输出c1 和 c2 就是答案

否则，我们需要在max(c1,c2) 和max(cc1,cc2)中间取最小值对应的值进行输出

好耶！完结撒花！！！ ヽ(✿ﾟ▽ﾟ)ノ✿ﾟ✿ﾟ✿ﾟ

附上源代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'

ll exgcd(ll a,ll b,ll &x,ll& y)
{
     if(b==0)
     {
     	x=1,y=0;
     	return a;
     }
     ll res=exgcd(b,a%b,y,x);
     y-=a/b*x;
     return res;
}
ll inv(ll n,ll p)
{
	ll x,y;
	ll bo=exgcd(n,p,x,y);
	if(bo!=1)return -1;
	else
	{
		return (x%p+p)%p;
	}
}
ll cheng(ll a,ll b,ll p)
{
	ll res=0;
	a%=p;
	while(b)
	{
		if(b&1)res=(res+a)%p;
		a=(2*a)%p;
		b>>=1;
	}
	return res;
}
ll n,m,k;
void solve()
{
	ll x,a,s;
	cin>>x>>a>>s;
	ll x0,y0;
	ll g=exgcd(a,s,x0,y0);//ax0+sy0=gcd(a,s);
	if(x%g!=0)
	{
		cout<<"No"<<endl;
	}else
	{
	ll dx=s/g;//最小步长 x=x0+k*dx y=y0-k*dy 之所以dx是s/g就是因为要相互抵消掉，dy同理
	ll dy=a/g;
    ll X=(cheng(x0,x/g,dx)%dx+dx)%dx;//最小满足正整数X aX+sY=x
    if(X>x/a)//如果最小的X都不能满足，即Y必须是正数则无解
    {
    	cout<<"No"<<endl;
    }else
    {
    	ll Y=(x-a*X)/s;
    	//如果我们想要两个人相遇时间最短，那么这个时间取决于两个人走的最慢的那个人
    	//也就是我们希望两个人的耗时最大的能尽可能小，那么，只有两个耗时最相近的时候
    	//他们的耗时最大值最小
    	//那么我们假设可以相等
    	//即  X+kdx = Y-kdy  ->  k（dx+dy）=Y-X
    	ll k = (Y-X)/(dx+dy);
    	//除法向下取整 所以k+1也可能是正解，需要判断取解
    	// k
        ll c1=X+k*dx;
        ll c2=Y-k*dy;
        //k+1
        ll cc1=X+(k+1)*dx;
        ll cc2=Y-(k+1)*dy;
        cout<<"Yes"<<endl;
        if(cc2<0)//如果k+1 让c2变成负数那答案就是k
        {
        	cout<<c1<<" "<<c2<<endl;
        }else
        {
        	if(max(c1,c2)<=max(cc1,cc2))
        	{
        		cout<<c1<<" "<<c2<<endl;
        	}else
        	{
        		cout<<cc1<<" "<<cc2<<endl;
        	}
        }
    }
	}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	ll T=1;
	cin>>T;
	while(T--)
	{
		solve();
	}
}