斩杀线计算大师

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

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

分析：

令，且，对于一个，存在非负整数的条件显然为且

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

做法：

令表示只用和能拼出的最小的，且，这样就有个点，考虑对于点之间连边：

，边权为，，边权为

然后从0开始跑最短路就可以求出数组，枚举每一个，如果满足且，此时就一定存在一个，然后也可以用扩展欧几里得定理解方程得到

时间复杂度为

#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;
}