题解 P6552 【文具订购（加强版）】

· · 题解

首先给出一个暴力的做法

枚举\ a\ b\ c\ 中的最小值 t ，设 r=n-t(x+y+z)，使用拓展欧几里得将 r 表示成 x,y 或 y,z 或 x,z 的线性组合，如果能够做到二者的系数非负，则表示找到了解。此时为了满足条件3，应该将较大的变量对应的系数最小化，然后拿来更新答案。

由于三组exgcd都可以拿到循环外面做，因此复杂度 O(\frac{n}{x+y+z})

我们再添加一个看起来是优化常数的东西：

从大到小枚举 t ，显然在条件2的约束下，如果找到了解应该直接break。

然后再特判根本没有整数解的情况，根据贝祖定理，就是 gcd(x,y,z)\nmid n

你会发现，这份代码神奇地通过了本题。

为什么呢？为了证明复杂度，我们需要回想一下 P3951小凯的疑惑 的结论

对于两个互质的正整数 a,b ，ax+by\ (x,y\in N) 最大的不能表示的数是 ab-a-b

也就是说，假设三个数两两互质，对应到这道题上，当 r\geq min(xy-x-y,yz-y-z,xz-x-z) 时一定能找到解

也就是说我们的复杂度变成了O(\frac{min(n,xy,yz,xz)}{x+y+z})

这有啥用呢？

当 xy,yz,xz 中全都 \geq n 时，一定有 x+y+z\geq \sqrt{n}，因此复杂度是 O(\sqrt n)

否则，不妨假设 min(xy,yz,xz) =xy，\frac{xy}{x+y+z}\leq \frac{xy}{x+y} \leq \frac{\sqrt{xy}}{2}，复杂度还是 O(\sqrt n)

那么如果除去三个数两两互质的情况，如何证明复杂度？

我们需要对上面的结论做一个比较显然的变换

对于两个正整数 a,b ，ax+by\ (x,y\in N) 最大的不能表示的 gcd(a,b) 的倍数是 \frac{ab}{gcd(a,b)}-a-b

我们发现，找到解所需的 r 的上界量级并没有增加，只不过多了一个限制：gcd(x,y)\mid r（这里只考虑求 x,y 的线性组合，其他的同理）

我们把r=n-t(x+y+z)带入一通分析，得到 tz\equiv n\ \rm mod gcd(x,y)

这是个线性方程组，解完之后大概形如t\equiv t_0\ \rm mod \frac{gcd(x,y)}{gcd(x,y,z)}

由于这个 t 是我们枚举的，这说明了在 r\geq \frac{xy}{gcd(x,y)}-x-y 之后我们至多再枚举 \frac{gcd(x,y)}{gcd(x,y,z)} 次，这个数肯定 \leq min(x,y)，进而在 xy\leq n 时在 \sqrt{n} 以内。将其代入刚才的复杂度论证的第二种情况，得到复杂度还是O(\sqrt n)的。

特别注意，做法中特判无解正好对应了关于 t 的线性方程无解的情况，这时循环次数就成了严格\frac{n}{x+y+z}次。不判是会超时的。

综上这题复杂度 O(\sqrt{n})

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
ll d;
pair<ll,ll> exgcd(ll a,ll b){
    if(!b){
        d=a;
        return {1,0};
    }
    pair<ll,ll> ret,ans=exgcd(b,a%b);
    ret.first=ans.second;
    ret.second=ans.first-(a/b)*ans.second;
    return ret;
}
ll ansa,ansb,ansc;
void upd(ll a,ll b,ll c){
    if(a+b+c>ansa+ansb+ansc){
        ansa=a;ansb=b;ansc=c;
    }
}
ll n,x,y,z;
pair<ll,ll> w1,w2,w3;
ll d1,d2,d3;
int main(){
    int i,j;
    int T;cin>>T;
    while(T--){
        cin>>n>>x>>y>>z;
        exgcd(x,y);exgcd(z,d);
        if(n%d){
            cout<<-1<<endl;
            continue;
        }
        ll t;ansa=ansb=ansc=0;
        w1=exgcd(x,y);d1=d;
        w2=exgcd(y,z);d2=d;
        w3=exgcd(x,z);d3=d;
        for(t=n/(x+y+z);t>=0;t--){
            ll r=n-t*(x+y+z);
            ll _x=w1.first,_y=w1.second;d=d1;
            if(r%d==0){
                _x*=(r/d);
                _x=(_x%(y/d)+(y/d))%(y/d);
                _y=(r-_x*x)/y;
                if(_y>=0) upd(t+_x,t+_y,t);
            }
            _x=w2.first;_y=w2.second;d=d2;
            if(r%d==0){
                _x*=(r/d);
                _x=(_x%(z/d)+(z/d))%(z/d);
                _y=(r-_x*y)/z;
                if(_y>=0) upd(t,t+_x,t+_y);
            }
            _x=w3.first;_y=w3.second;d=d3;
            if(r%d==0){
                _x*=(r/d);
                _x=(_x%(z/d)+(z/d))%(z/d);
                _y=(r-_x*x)/z;
                if(_y>=0) upd(t+_x,t,t+_y);
            }
            if(ansa*x+ansb*y+ansc*z==n){
                cout<<ansa<<" "<<ansb<<" "<<ansc<<endl;
                break;
            }
        }
        if(t<0)
            cout<<-1<<endl;
    }
    return 0;
}

upd：这篇文章中介绍了一种基于类欧几里得的O(log^2n)的做法