自动搬运

查看原文

来自洛谷，原作者为

	Aw顿顿 直须看尽洛城花，始共春风容易别

搬运于2025-08-24 22:07:53，当前版本为作者最后更新于2021-01-19 15:29:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前置知识

【提高数学】类欧几里得算法的盛宴

题意简述

给定 $a,b,c$，求 $ax+by \le c$ 非负整数解的个数，我们可以转换：

$$ax+by \le c\ \to\ by\le c-ax$$ $$by\le c-ax\ \to\ y\le\left\lfloor{\dfrac{c-ax}{b}}\right\rfloor $$

对于 $y$，合法的 $x$ 的个数是 $\left\lfloor{\dfrac{c-ax}{b}}\right\rfloor+1$，之所以要 $+1$ 是因为符号是 $\le$。

令 $y=0$，此时存在 $ax\le c$，即 $x\le\left\lfloor\dfrac{c}{a}\right\rfloor$，那么我们需要枚举的 $x$ 范围是 $0\sim\left\lfloor\dfrac{c}{a}\right\rfloor$。

进一步将要求的量表述出来，即在每一个 $x$ 的情况下，计算存在多少个合法解，即：

$$\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor{\dfrac{c-ax}{b}}\right\rfloor+1 $$

诶，长得，是不是有点像类欧？然而你也不能直接把 $-b$ 代入计算，那么我们转换，用类似于 JZP 题解的方式，在分子加入 $bx$，在外部减去 $\left\lfloor{\dfrac{bx}{b}}\right\rfloor$，即 $x$，式子就变成：

$$\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor{\dfrac{(b-a)x+c}{b}}\right\rfloor-x+1 $$

为了能用类欧，我们需要让 $b-a>0$，那么就在 $b<a$ 时使用 $\text{swap}(a,b)$，这样就处理完毕。对于式子的第一部分：

$$\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor{\dfrac{(b-a)x+c}{b}}\right\rfloor $$

已经可以用 $\text{Akin\ Euclidean}(b-a,c,b,\frac{a}{c})$ 来解决了。

但我们发现这个 $x$ 不好处理，于是我们单独拿出来：

$$\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}-x+1 $$

用基本的等差数列来求和得到：

$$\dfrac{\left(0+\left\lfloor\frac{c}{a}\right\rfloor\right)\times\left(\left\lfloor\frac{c}{a}\right\rfloor+1\right)}{2}+\left\lfloor\frac{c}{a}\right\rfloor $$

其中，大概是这样：

• $0$ 是首项

• $\left\lfloor\frac{c}{a}\right\rfloor$ 是末项

• 项数是 $\left\lfloor\frac{c}{a}\right\rfloor+1$

• 在这个式子后的那个 $\left\lfloor\frac{c}{a}\right\rfloor$ 是 $1$ 对整个求和式子的贡献

那么我们直接套到原式当中就是：

$$\left(\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor{\dfrac{(b-a)x+c}{b}}\right\rfloor\right)+\dfrac{\left\lfloor\frac{c}{a}\right\rfloor\left(\left\lfloor\frac{c}{a}\right\rfloor+1\right)}{2}+\left\lfloor\frac{c}{a}\right\rfloor $$

那么推导结束。

代码实现

如下，其中的 $f$ 函数就是类欧几里得函数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,c,s;
int f(int a,int b,int c,int n){
    if(a==0)return((b/c)*(n+1));
    if(a>=c||b>=c)return f(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
    int m=(a*n+b)/c;
    return n*m-f(c,c-b-1,a,m-1);
}signed main() {
	cin>>a>>b>>c;if(b<a)swap(b,a);
	cout<<f(b-a,c,b,c/a)-(c/a)*(c/a+1)/2+(c/a)+1<<endl;
	return 0;
}