# 同餘最短路

> 題目:給三個數字$x,y,z$，每個數字可以被加任意次，求總和有多少種可能在區間$[1,K]$

假設$k<=K$、$a_i$為任意數，則題目原式為:
$$xa_1+ya_2+za_3=k$$

我們不妨先假設$x<y<z$

初步的概念是枚舉$y$和$z$的數量，這樣會得到一個總和$sum(=ya_2+za_3)$，接著另$rest=K-sum$，代表剩餘的量，這些都會由$x$構成，因此枚舉$y$和$z$組合構成答案的數量等於$x$還能枚舉多少，也就是$\frac{rest}{x}+1$ ($+1$是因為$a_1$=0的時候)。

接下來我們可以把$sum\ mod\ x$，這樣方便於我們可以直接用上述公式計算($sum$超過$x$的幾倍可直接在枚舉$x$的時候補回來)，因此我們現在的問題變成計算所有在區間$[0,x-1]$中的$sum$，答案就是$\frac{k-sum_i}{x}+1\ (0 <=i < x)$ 的總和，那為了答案的完整性，對於每一個$mod\ x$後一樣的$sum$，要找最小的，這樣才能枚舉盡可能多的$x$，答案也才會是完整的。

那既然要找最小的$sum$，就可以用最短路徑演算法，我們基於在當前點$i$，加一條邊長度是$y$並且會通到$(i+y)\%x$的邊和一條邊長度是$z$並且會通到$(i+z)\%x$的邊，就會得到一張有向圖：

  y
i--->(i+y)mod(x)

  z
i--->(i+z)mod(x)

因為我們只要求$[0,x-1]$的範圍所以要$mod\ x$

最後，答案就是
$$\displaystyle\sum_{i=0} ^{x-1}(\frac{K-sum\ mod\ x=i中的最短路}{x})+1$$

[模板題](https://www.luogu.com.cn/problem/P3403#submit)

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pb push_back
#define pii pair<int, int>

const int MAXN = 100005;

vector<pii> Graph[MAXN];


signed main() {
    int x, y, z, k;
    cin >> k >> x >> y >> z;
    k--;
    if (x > y) swap(x, y);
    if (x > z) swap(x, z);
    if (y > z) swap(y, z);
    for (int i = 0; i < x; i++) {
        Graph[i].pb({(i + y) % x, y});
        Graph[i].pb({(i + z) % x, z});
    }

    int start = 0;

    vector<int> dis(x, LLONG_MAX);
    dis[start] = 0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({dis[start], start});

    while (!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        int d = cur.first, u = cur.second;
        if (dis[u] < d) continue;

        for (pii nxt : Graph[u]) {
            int v = nxt.first, w = nxt.second;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < x; i++) {
        if (dis[i] > k) continue;
        ans += (k - dis[i]) / x + 1;
    }
    cout << ans << ' ';
}