斩杀线计算大师

~~这道题纯数学的做法都有点玄学，感觉要么就是时间复杂度有点问题要么就是正确性有些问题~~

下面给出同余最短路的做法

分析：

令 $ax +by = p$ ，且 $x,y\ge 0$ ，对于一个 $p$ ，存在非负整数 $z$ 的条件显然为 $p\le k$ 且 $(k - p) \% c=0$

将 $p$ 按照对 $c$ 取模分类，可以发现，如果 $p_1\equiv p_2,\pmod c$ ，那么 $(k-p_1)\equiv (k -p_2),\pmod c$ ，因为要满足上面两个条件才存在 $z$ ，那么 $p$ 越小越好；换言之，我们需要求出模c同余的p中最小的那个

做法：

令 $f[i]$ 表示只用 $a$ 和 $b$ 能拼出的最小的 $p$ ，且 $p\%c = i$ ，这样就有 $c$ 个点，考虑对于点之间连边：

$i\to (i + a) \% c$ ，边权为 $a$ ， $i \to (i + b) \% c$ ，边权为 $b$

然后从0开始跑最短路就可以求出 $f[i]$ 数组，枚举每一个 $f$ ，如果满足 $f \le k$ 且 $(k - f) \%c =0$ ，此时就一定存在一个 $z$ ，然后 $x,y$ 也可以用扩展欧几里得定理解方程得到

时间复杂度为 $O(clogc)$

#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
ll a,b,c,k;
ll dis[N];
bool vis[N];

struct Edge
{
    int next,to; ll dis;
}edge[N << 3]; int head[N],cnt;
void add_edge(int from,int to,ll dis)
{
    edge[++cnt].next = head[from];
    edge[cnt].to = to;
    edge[cnt].dis = dis;
    head[from] = cnt;
}
void dijkstra(int s)
{
    priority_queue< pair<ll,int> > q;
    memset(dis,100,sizeof(dis));
    dis[s] = 0; q.push(make_pair(0,s));
    while(!q.empty())
    {
        int u = q.top().second; q.pop();
        if(vis[u]) continue; vis[u] = 1;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].dis)
            {
                dis[v] = dis[u] + edge[i].dis;
                if(!vis[v]) q.push(make_pair(-dis[v],v));
            }
        }
    }
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b) { x = 1; y = 0; return a; }
    ll d = exgcd(b,a % b,x,y);
    ll t = x; x = y; y = t - a / b * y;
    return d;
}

int main()
{
    cin>>a>>b>>c>>k;
    for(int i=0;i<c;++i)
    {
        add_edge(i,(i + a) % c,a);
        add_edge(i,(i + b) % c,b);
    }
    dijkstra(0);
    for(int i=0;i<c;++i)
    {
        if(dis[i] <= k && (k - dis[i]) % c == 0)
        {
            ll x,y,z,d;
            d = exgcd(a,b,x,y);
            x = ((dis[i] / d) * x % (b / d) + (b / d)) % (b / d);
            y = (dis[i] - a * x) / b;
            z = (k - dis[i]) / c;
            cout<<x<<' '<<y<<' '<<z<<endl;
            break;
        }
    }
    return 0;
}