三种奖券：从暴力枚举n³到logM

问题描述

给定三种奖券，面额分别为正整数 $a,b,c$，每种可取任意张。目标总分为 $s$，其中$0\le s\le 10^9.$

求方程 $ax+by+cz=s$ 的解的个数。

三种奖券按种类区分。即使面额相同，不同的取用数量三元组 $(x,y,z)$ 仍算不同方案。

答案范围与整数类型

由于 $a,b,c\ge1$，任何合法解都满足 $x+y\le s$。固定 $(x,y)$ 后，$z$ 至多有一个合法值，因此

$$\begin{aligned} \operatorname{ways}(s) &\le \sum_{x=0}^{s}(s-x+1) &=\frac{(s+1)(s+2)}2. \end{aligned}$$

当 $a=b=c=1$ 时取到等号。于是最大答案为

$$\frac{(10^9+1)(10^9+2)}2 =500\,000\,001\,500\,000\,001,$$

可以用 long long 保存。下面的代码用 long long 读取输入，系数乘法和整除求和的中间量统一使用 __int128。

五种方法概览

记

记$D=\max\{a,b,c\},M=\max\{a,b,c,s,2\}$

• 方法 1 ：枚举三个变量， $O((\frac{s}{a}+1)(\frac{s}{b}+1)(\frac{s}{c}+1))$
• 方法 2 ：枚举两个变量，计算第三个， $O((\frac{s}{a}+1)(\frac{s}{b}+1))$
• 方法 3 ：枚举一种，公式计算二元方程解数， $O(1+\frac{s}{D}+\log M)$
• 方法 4 ：完全背包 DP， $O(s+1)$
• 方法 5 ：同余筛选与整除求和， $O(\log M)$

以下代码使用 C++17，记 ll = long long、i128 = __int128。方法 3 使用的 floorDiv、invMod 定义见末尾完整代码。

方法 1：三重循环

三个变量分别满足

$$0\le x\le\left\lfloor\frac{s}{a}\right\rfloor,\qquad 0\le y\le\left\lfloor\frac{s}{b}\right\rfloor,\qquad 0\le z\le\left\lfloor\frac{s}{c}\right\rfloor.$$

逐一枚举并检查即可。

ll solve1(ll a, ll b, ll c, ll s) {
    ll ans = 0;
    for (ll x = 0; x <= s / a; x++)
        for (ll y = 0; y <= s / b; y++)
            for (ll z = 0; z <= s / c; z++)
                if (a * x + b * y + c * z == s)
                    ans++
    return ans;
}

当 $a=b=c=1$ 时，循环次数为 $(s+1)^3$，无法处理较大的 $s$。

方法 2：消去一个变量

固定 $x,y$，令 $r=s-ax-by$

若 $r\ge0$ 且 $c\mid r$，则有唯一的合法值 $z=r/c$。否则无解。

让内层循环的上界保证剩余分数非负，就只需检查整除条件。

ll solve2(ll a, ll b, ll c, ll s) {
    ll ans = 0;
    for (ll x = 0; x <= s / a; x++) {
        ll r = s - a * x;
        for (ll y = 0; y <= r / b; y++)
            if ((r - b * y) % c == 0) 
                ans++;
    }
    return ans;
}

最坏情况下仍需平方级枚举。下一步是用公式一次算出整个内层循环的贡献。

方法 3：枚举一种，计算二元方程解数

固定 $x$ 后，需要计算 $by+cz=r,r=s-ax$ 的非负整数解个数。

1. 约去最大公因数

令 $g=\gcd(b,c)$。若 $g\nmid r$，则无解；否则令

$$B=\frac bg,\qquad C=\frac cg,\qquad n=\frac rg.$$

方程化为

$$By+Cz=n,\qquad \gcd(B,C)=1.$$

2. 写出全部整数解

取整数 $U,V$，满足

$$BU+CV=1.$$

当 $C>1$ 时，可以取

$$U=B^{-1}\bmod C,\qquad V=\frac{1-BU}{C},$$

其中 $0\le U<C$。当 $C=1$ 时，直接取 $U=0,V=1$。

将等式乘以 $n$，得到全部整数解

$$y=Un+Ck,\qquad z=Vn-Bk,\qquad k\in\mathbb Z.$$

3. 用非负条件确定参数范围

由 $y,z\ge0$，有

$$\left\lceil-\frac{Un}{C}\right\rceil \le k\le \left\lfloor\frac{Vn}{B}\right\rfloor.$$

利用 $\lceil-t\rceil=-\lfloor t\rfloor$，得到

$$\operatorname{count}(n) =1+\left\lfloor\frac{Un}{C}\right\rfloor +\left\lfloor\frac{Vn}{B}\right\rfloor.$$

这里不需要再取 $\max(0,\cdot)$。因为 $n\ge0$，实数区间的长度为

$$\frac{Vn}{B}-\left(-\frac{Un}{C}\right) =\frac{n(BU+CV)}{BC} =\frac{n}{BC}\ge0.$$

因此整数计数公式不会为负；区间内没有整数时，结果恰好为零。

注意：$V$ 可能为负数，必须使用数学意义的向下取整，不能直接依赖 C++ 对负数的整数除法。

代码

把最大面额放在 $a$ 的位置，使外层枚举次数最少。

ll solve3(ll a, ll b, ll c, ll s) {
    array<ll, 3> f{a, b, c};
    sort(f.begin(), f.end());
    a = f[2]; b = f[0]; c = f[1];

    ll g = gcd(b, c), B = b / g, C = c / g;
    ll U = 0;
    i128 V = 1;
    if (C > 1) {
        U = invMod(B, C);
        V = (1 - (i128)B * U) / C;
    }

    i128 ans = 0;
    for (ll x = 0; x <= s / a; x++) {
        ll r = s - a * x;
        if (r % g != 0) continue;

        ll n = r / g;
        ans += 1 + floorDiv((i128)U * n, C) + floorDiv(V * n, B);
    }
    return (ll)ans;
}

当三种面额都很小时，外层循环仍然较长。方法 5 会把这个循环也转化为公式。

方法 4：完全背包 DP

令 $f[j]$ 表示使用已经处理的奖券种类，凑出 $j$ 分的方案数。

初始状态为

$$f[0]=1,\qquad f[j]=0\quad(j>0).$$

对于每一种面额 $v$，按分数递增更新

$$f[j]\leftarrow f[j]+f[j-v],\qquad j=v,v+1,\ldots,s.$$

ll solve4(ll a, ll b, ll c, ll s) {
    vector<ll> f(s + 1, 0);
    f[0] = 1;
    for (ll v : {a, b, c})
        for (ll j = v; j <= s; j++)
            f[j] += f[j - v];
    return f[s];
}

两层循环各有作用：

• 种类在外层：每个数量组合只计数一次。
• 分数递增：允许当前种类重复取用。

时间和空间复杂度均为 $O(s+1)$，不适合本题中最大的目标分数。

方法 5：同余筛选与整除求和

1. 把枚举变量筛成等差数列

仍令 $g=\gcd(b,c)$。因为 $by+cz$ 必须是 $g$ 的倍数，所以

$$ax\equiv s\pmod g.$$

令

$$h=\gcd(a,g)=\gcd(a,b,c),\qquad d=\frac gh.$$

若 $h\nmid s$，原方程无解；否则约去 $h$，得到

$$\frac ahx\equiv\frac sh\pmod d.$$

由于 $\gcd(a/h,d)=1$，最小非负解为

$$x_0= \begin{cases} 0,&d=1,\\[4pt] \displaystyle\left(\frac sh\left(\frac ah\right)^{-1}\right)\bmod d,&d>1. \end{cases}$$

所有非负候选都可以写成

$$x=x_0+dt,\qquad t\in\mathbb Z_{\ge0}.$$

如果 $ax_0>s$，最小候选已经超出目标，直接返回零。

2. 把每个候选的贡献写成两个取整式

定义

$$A=\frac ah,\qquad B=\frac bg,\qquad C=\frac cg,\qquad R=\frac{s-ax_0}{g}.$$

代回原方程，并利用 $\frac{ad}{g}=\frac{a}{h}=A$，得到

$$By+Cz=R-At.$$

右端非负要求

$$0\le t\le\left\lfloor\frac RA\right\rfloor.$$

因此候选个数为

$$N=\left\lfloor\frac RA\right\rfloor+1.$$

继续使用 $BU+CV=1$，每个候选的贡献为

$$\operatorname{count}(R-At) =1+\left\lfloor\frac{UR-UA\,t}{C}\right\rfloor +\left\lfloor\frac{VR-VA\,t}{B}\right\rfloor.$$

定义整除求和函数

$$F(n,m,p,q)=\sum_{i=0}^{n-1}\left\lfloor\frac{pi+q}{m}\right\rfloor, \qquad n\ge0,\ m>0.$$

其中 $p,q$ 允许为负数。总方案数就变为

$$\operatorname{ways} =N+F(N,C,-UA,UR)+F(N,B,-VA,VR).$$

问题转化为：如何快速计算 $F$？

3. 整倍数分离

按数学意义的带余除法，写成

$$p=um+p',\qquad q=vm+q',\qquad 0\le p',q'<m,$$

其中

$$u=\left\lfloor\frac pm\right\rfloor,\qquad v=\left\lfloor\frac qm\right\rfloor.$$

逐项分离整数部分，得到

$$F(n,m,p,q) =u\frac{n(n-1)}2+vn+F(n,m,p',q').$$

即使 $p,q$ 为负数，这个公式也成立。

4. 换序计数

下面假设已经归一化为 $0\le p,q<m$。令

$$Y=pn+q,\qquad L=\left\lfloor\frac Ym\right\rfloor,\qquad r=Y\bmod m.$$

若 $Y<m$，每一项均为零，可以直接结束。特别地，$p=0$ 时一定在这里结束，不会出现除以零。

否则 $p>0$。把每项取整看成满足 $mj\le pi+q$ 的正整数 $j$ 的个数，交换计数顺序：

$$\begin{aligned} F(n,m,p,q) &=\sum_{j=1}^{L}\left\lfloor\frac{Y-mj}{p}\right\rfloor\\ &=\sum_{k=0}^{L-1}\left\lfloor\frac{mk+r}{p}\right\rfloor\\ &=F(L,p,m,r). \end{aligned}$$

其中第二步使用了 $Y=mL+r$ 和 $k=L-j$。

因此，一轮变换为

$$(n,m,p,q)\longleftarrow(L,p,m,r).$$

新的除数是原来的 $p<m$。结合下一轮的取模操作，整个过程沿欧几里得算法递降，复杂度为 $O(\log m)$。

完整代码

#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
using namespace std;

using ll = long long;
using i128 = __int128;

// m > 0；按数学定义向下取整。
i128 floorDiv(i128 a, i128 m) {
    return a / m - (a % m < 0);
}

// m > 1 且 gcd(a, m) = 1。
ll invMod(ll a, ll m) {
    i128 r0 = a % m, r1 = m;
    i128 u0 = 1, u1 = 0;
    while (r1 != 0) {
        i128 k = r0 / r1;
        i128 r2 = r0 - k * r1;
        i128 u2 = u0 - k * u1;
        r0 = r1; r1 = r2;
        u0 = u1; u1 = u2;
    }
    u0 %= m;
    if (u0 < 0) u0 += m;
    return (ll)u0;
}

// n >= 0，m > 0；p、q 可以为负数。
i128 floorSum(i128 n, i128 m, i128 p, i128 q) {
    i128 ans = 0;
    while (true) {
        i128 u = floorDiv(p, m);
        i128 v = floorDiv(q, m);
        ans += u * n * (n - 1) / 2 + v * n;
        p -= u * m;
        q -= v * m;

        i128 Y = p * n + q;
        if (Y < m) return ans;

        n = Y / m;
        q = Y % m;
        swap(m, p);
    }
}

ll solve(ll a, ll b, ll c, ll s) {
    // 交换面额不会改变解的个数；最大面额放在枚举变量处。
    array<ll, 3> f{a, b, c};
    sort(f.begin(), f.end());
    a = f[2]; b = f[0]; c = f[1];

    ll g = gcd(b, c);
    ll h = gcd(a, g);
    if (s % h != 0) return 0;

    ll d = g / h;
    ll x0 = 0;
    if (d > 1) 
        x0 = (ll)((i128)(s / h) * invMod(a / h, d) % d);
    if ((i128)a * x0 > s) 
        return 0;

    ll A = a / h;
    ll B = b / g;
    ll C = c / g;
    ll R = (ll)(((i128)s - (i128)a * x0) / g);
    ll N = R / A + 1;

    ll U = 0;
    i128 V = 1;
    if (C > 1) {
        U = invMod(B, C);
        V = (1 - (i128)B * U) / C;
    }

    i128 ans = (i128)N + floorSum(N, C, -(i128)U * A, (i128)U * R) + floorSum(N, B, -V * A, V * R);
    return (ll)ans;
}

int main() {
    ll a, b, c, s;
    if (!(cin >> a >> b >> c >> s)) return 0;
    cout << solve(a, b, c, s) << '\n';
}

时间复杂度为 $O(\log M)$。