同餘最短路

題目:給三個數字\(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\]

模板題






















































#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 << ' ';
}
Select a repo