问题描述
给定三种奖券，面额分别为正整数 a,b,ca,b,ca,b,c，每种可取任意张。目标总分为 sss，其中0≤s≤109.0\le s\le 10^9.0≤s≤109.
求方程 ax+by+cz=sax+by+cz=sax+by+cz=s 的解的个数。
三种奖券按种类区分。即使面额相同，不同的取用数量三元组 (x,y,z)(x,y,z)(x,y,z) 仍算不同方案。
答案范围与整数类型
由于 a,b,c≥1a,b,c\ge1a,b,c≥1，任何合法解都满足 x+y≤sx+y\le sx+y≤s。固定 (x,y)(x,y)(x,y) 后，zzz 至多有一个合法值，因此
ways(s)≤∑x=0s(s−x+1)=(s+1)(s+2)2.\begin{aligned} \operatorname{ways}(s) &\le \sum_{x=0}^{s}(s-x+1) &=\frac{(s+1)(s+2)}2. \end{aligned} ways(s) ≤x=0∑s (s−x+1) =2(s+1)(s+2) .
当 a=b=c=1a=b=c=1a=b=c=1 时取到等号。于是最大答案为
(109+1)(109+2)2=500 000 001 500 000 001,\frac{(10^9+1)(10^9+2)}2 =500\,000\,001\,500\,000\,001, 2(109+1)(109+2) =500000001500000001,
可以用 long long 保存。下面的代码用 long long 读取输入，系数乘法和整除求和的中间量统一使用 __int128。
五种方法概览
记
记D=max{a,b,c},M=max{a,b,c,s,2}D=\max\{a,b,c\},M=\max\{a,b,c,s,2\}D=max{a,b,c},M=max{a,b,c,s,2}
* 方法 1 ：枚举三个变量， O((sa+1)(sb+1)(sc+1))O((\frac{s}{a}+1)(\frac{s}{b}+1)(\frac{s}{c}+1))O((as +1)(bs +1)(cs +1))
* 方法 2 ：枚举两个变量，计算第三个， O((sa+1)(sb+1))O((\frac{s}{a}+1)(\frac{s}{b}+1))O((as +1)(bs +1))
* 方法 3 ：枚举一种，公式计算二元方程解数， O(1+sD+logM)O(1+\frac{s}{D}+\log M)O(1+Ds +logM)
* 方法 4 ：完全背包 DP， O(s+1)O(s+1)O(s+1)
* 方法 5 ：同余筛选与整除求和， O(logM)O(\log M)O(logM)
以下代码使用 C++17，记 ll = long long、i128 = __int128。方法 3 使用的 floorDiv、invMod 定义见末尾完整代码。
方法 1：三重循环
三个变量分别满足
0≤x≤⌊sa⌋,0≤y≤⌊sb⌋,0≤z≤⌊sc⌋.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. 0≤x≤⌊as ⌋,0≤y≤⌊bs ⌋,0≤z≤⌊cs ⌋.
逐一枚举并检查即可。
当 a=b=c=1a=b=c=1a=b=c=1 时，循环次数为 (s+1)3(s+1)^3(s+1)3，无法处理较大的 sss。
方法 2：消去一个变量
固定 x,yx,yx,y，令 r=s−ax−byr=s-ax-byr=s−ax−by
若 r≥0r\ge0r≥0 且 c∣rc\mid rc∣r，则有唯一的合法值 z=r/cz=r/cz=r/c。否则无解。
让内层循环的上界保证剩余分数非负，就只需检查整除条件。
最坏情况下仍需平方级枚举。下一步是用公式一次算出整个内层循环的贡献。
方法 3：枚举一种，计算二元方程解数
固定 xxx 后，需要计算 by+cz=r,r=s−axby+cz=r,r=s-axby+cz=r,r=s−ax 的非负整数解个数。
1. 约去最大公因数
令 g=gcd(b,c)g=\gcd(b,c)g=gcd(b,c)。若 g∤rg\nmid rg∤r，则无解；否则令
B=bg,C=cg,n=rg.B=\frac bg,\qquad C=\frac cg,\qquad n=\frac rg. B=gb ,C=gc ,n=gr .
方程化为
By+Cz=n,gcd(B,C)=1.By+Cz=n,\qquad \gcd(B,C)=1. By+Cz=n,gcd(B,C)=1.
2. 写出全部整数解
取整数 U,VU,VU,V，满足
BU+CV=1.BU+CV=1. BU+CV=1.
当 C>1C>1C>1 时，可以取
U=B−1 mod C,V=1−BUC,U=B^{-1}\bmod C,\qquad V=\frac{1-BU}{C}, U=B−1modC,V=C1−BU ,
其中 0≤U<C0\le U<C0≤U<C。当 C=1C=1C=1 时，直接取 U=0,V=1U=0,V=1U=0,V=1。
将等式乘以 nnn，得到全部整数解
y=Un+Ck,z=Vn−Bk,k∈Z.y=Un+Ck,\qquad z=Vn-Bk,\qquad k\in\mathbb Z. y=Un+Ck,z=Vn−Bk,k∈Z.
3. 用非负条件确定参数范围
由 y,z≥0y,z\ge0y,z≥0，有
⌈−UnC⌉≤k≤⌊VnB⌋.\left\lceil-\frac{Un}{C}\right\rceil \le k\le \left\lfloor\frac{Vn}{B}\right\rfloor. ⌈−CUn ⌉≤k≤⌊BVn ⌋.
利用 ⌈−t⌉=−⌊t⌋\lceil-t\rceil=-\lfloor t\rfloor⌈−t⌉=−⌊t⌋，得到
count(n)=1+⌊UnC⌋+⌊VnB⌋.\operatorname{count}(n) =1+\left\lfloor\frac{Un}{C}\right\rfloor +\left\lfloor\frac{Vn}{B}\right\rfloor. count(n)=1+⌊CUn ⌋+⌊BVn ⌋.
这里不需要再取 max(0,⋅)\max(0,\cdot)max(0,⋅)。因为 n≥0n\ge0n≥0，实数区间的长度为
VnB−(−UnC)=n(BU+CV)BC=nBC≥0.\frac{Vn}{B}-\left(-\frac{Un}{C}\right) =\frac{n(BU+CV)}{BC} =\frac{n}{BC}\ge0. BVn −(−CUn )=BCn(BU+CV) =BCn ≥0.
因此整数计数公式不会为负；区间内没有整数时，结果恰好为零。
注意：VVV 可能为负数，必须使用数学意义的向下取整，不能直接依赖 C++ 对负数的整数除法。
代码
把最大面额放在 aaa 的位置，使外层枚举次数最少。
当三种面额都很小时，外层循环仍然较长。方法 5 会把这个循环也转化为公式。
方法 4：完全背包 DP
令 f[j]f[j]f[j] 表示使用已经处理的奖券种类，凑出 jjj 分的方案数。
初始状态为
f[0]=1,f[j]=0(j>0).f[0]=1,\qquad f[j]=0\quad(j>0). f[0]=1,f[j]=0(j>0).
对于每一种面额 vvv，按分数递增更新
f[j]←f[j]+f[j−v],j=v,v+1,…,s.f[j]\leftarrow f[j]+f[j-v],\qquad j=v,v+1,\ldots,s. f[j]←f[j]+f[j−v],j=v,v+1,…,s.
两层循环各有作用：
* 种类在外层：每个数量组合只计数一次。
* 分数递增：允许当前种类重复取用。
时间和空间复杂度均为 O(s+1)O(s+1)O(s+1)，不适合本题中最大的目标分数。
方法 5：同余筛选与整除求和
1. 把枚举变量筛成等差数列
仍令 g=gcd(b,c)g=\gcd(b,c)g=gcd(b,c)。因为 by+czby+czby+cz 必须是 ggg 的倍数，所以
ax≡s(modg).ax\equiv s\pmod g. ax≡s(modg).
令
h=gcd(a,g)=gcd(a,b,c),d=gh.h=\gcd(a,g)=\gcd(a,b,c),\qquad d=\frac gh. h=gcd(a,g)=gcd(a,b,c),d=hg .
若 h∤sh\nmid sh∤s，原方程无解；否则约去 hhh，得到
ahx≡sh(modd).\frac ahx\equiv\frac sh\pmod d. ha x≡hs (modd).
由于 gcd(a/h,d)=1\gcd(a/h,d)=1gcd(a/h,d)=1，最小非负解为
x0={0,d=1,(sh(ah)−1) mod d,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} x0 =⎩⎨⎧ 0,(hs (ha )−1)modd, d=1,d>1.
所有非负候选都可以写成
x=x0+dt,t∈Z≥0.x=x_0+dt,\qquad t\in\mathbb Z_{\ge0}. x=x0 +dt,t∈Z≥0 .
如果 ax0>sax_0>sax0 >s，最小候选已经超出目标，直接返回零。
2. 把每个候选的贡献写成两个取整式
定义
A=ah,B=bg,C=cg,R=s−ax0g.A=\frac ah,\qquad B=\frac bg,\qquad C=\frac cg,\qquad R=\frac{s-ax_0}{g}. A=ha ,B=gb ,C=gc ,R=gs−ax0 .
代回原方程，并利用 adg=ah=A\frac{ad}{g}=\frac{a}{h}=Agad =ha =A，得到
By+Cz=R−At.By+Cz=R-At. By+Cz=R−At.
右端非负要求
0≤t≤⌊RA⌋.0\le t\le\left\lfloor\frac RA\right\rfloor. 0≤t≤⌊AR ⌋.
因此候选个数为
N=⌊RA⌋+1.N=\left\lfloor\frac RA\right\rfloor+1. N=⌊AR ⌋+1.
继续使用 BU+CV=1BU+CV=1BU+CV=1，每个候选的贡献为
count(R−At)=1+⌊UR−UA tC⌋+⌊VR−VA tB⌋.\operatorname{count}(R-At) =1+\left\lfloor\frac{UR-UA\,t}{C}\right\rfloor +\left\lfloor\frac{VR-VA\,t}{B}\right\rfloor. count(R−At)=1+⌊CUR−UAt ⌋+⌊BVR−VAt ⌋.
定义整除求和函数
F(n,m,p,q)=∑i=0n−1⌊pi+qm⌋,n≥0, m>0.F(n,m,p,q)=\sum_{i=0}^{n-1}\left\lfloor\frac{pi+q}{m}\right\rfloor, \qquad n\ge0,\ m>0. F(n,m,p,q)=i=0∑n−1 ⌊mpi+q ⌋,n≥0, m>0.
其中 p,qp,qp,q 允许为负数。总方案数就变为
ways=N+F(N,C,−UA,UR)+F(N,B,−VA,VR).\operatorname{ways} =N+F(N,C,-UA,UR)+F(N,B,-VA,VR). ways=N+F(N,C,−UA,UR)+F(N,B,−VA,VR).
问题转化为：如何快速计算 FFF？
3. 整倍数分离
按数学意义的带余除法，写成
p=um+p′,q=vm+q′,0≤p′,q′<m,p=um+p',\qquad q=vm+q',\qquad 0\le p',q'<m, p=um+p′,q=vm+q′,0≤p′,q′<m,
其中
u=⌊pm⌋,v=⌊qm⌋.u=\left\lfloor\frac pm\right\rfloor,\qquad v=\left\lfloor\frac qm\right\rfloor. u=⌊mp ⌋,v=⌊mq ⌋.
逐项分离整数部分，得到
F(n,m,p,q)=un(n−1)2+vn+F(n,m,p′,q′).F(n,m,p,q) =u\frac{n(n-1)}2+vn+F(n,m,p',q'). F(n,m,p,q)=u2n(n−1) +vn+F(n,m,p′,q′).
即使 p,qp,qp,q 为负数，这个公式也成立。
4. 换序计数
下面假设已经归一化为 0≤p,q<m0\le p,q<m0≤p,q<m。令
Y=pn+q,L=⌊Ym⌋,r=Y mod m.Y=pn+q,\qquad L=\left\lfloor\frac Ym\right\rfloor,\qquad r=Y\bmod m. Y=pn+q,L=⌊mY ⌋,r=Ymodm.
若 Y<mY<mY<m，每一项均为零，可以直接结束。特别地，p=0p=0p=0 时一定在这里结束，不会出现除以零。
否则 p>0p>0p>0。把每项取整看成满足 mj≤pi+qmj\le pi+qmj≤pi+q 的正整数 jjj 的个数，交换计数顺序：
F(n,m,p,q)=∑j=1L⌊Y−mjp⌋=∑k=0L−1⌊mk+rp⌋=F(L,p,m,r).\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} F(n,m,p,q) =j=1∑L ⌊pY−mj ⌋=k=0∑L−1 ⌊pmk+r ⌋=F(L,p,m,r).
其中第二步使用了 Y=mL+rY=mL+rY=mL+r 和 k=L−jk=L-jk=L−j。
因此，一轮变换为
(n,m,p,q)⟵(L,p,m,r).(n,m,p,q)\longleftarrow(L,p,m,r). (n,m,p,q)⟵(L,p,m,r).
新的除数是原来的 p<mp<mp<m。结合下一轮的取模操作，整个过程沿欧几里得算法递降，复杂度为 O(logm)O(\log m)O(logm)。
完整代码
时间复杂度为 O(logM)O(\log M)O(logM)。
