「Luogu 5171」Earthquake

Description

题目链接:Luogu 5171

给定 $a,b,c$,求满足方程 $ax+by\le c$ 的非负整数解个数。

数据范围:$1\le a,b\le 10^9$,$0\le c\le \min(a,b)\times 10^9$


Solution

通过简单的线性规划知识,我们可以得到方程组:

分析可以得到答案为直线 $ax+by=c$(斜率显然是负数)与 $x$ 轴、$y$ 轴围成的图形中的整点数(包括边界)。也就是答案为(前一部分为 $x$ 轴上的点的个数):

是不是很像类欧几里德算法?具体推导过程详见:「算法笔记」类欧几里德算法

但是这样 $\sum$ 里是会有负数的。不信你按照类欧的公式推一下?$f(a,b,c,n)$ 是会递归到 $f\left(c,c-b-1,a,\left\lfloor\frac{an+b}{c}\right\rfloor-1\right)$ 的,这样递归之后直线在 $y$ 轴的截距就是负数了(如果是负数还要和 $0$ 取 $\max$……)。

我们把这个函数变成增函数。把 $x=0$ 和 $x=\left\lfloor\frac{c}{a}\right\rfloor$ 时函数上的两点对换,得到函数 $y=\frac{ax+c\bmod a}{b}$,故原式化为:

后半部分就是类欧几里德算法中的函数:

时间复杂度:$O(\log a)$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
typedef long long LL;

LL F(LL a,LL b,LL c,LL n) {
if(a==0) return b/c*(n+1);
if(a>=c||b>=c) return a/c*n*(n+1)/2+b/c*(n+1)+F(a%c,b%c,c,n);
LL m=(a*n+b)/c;
return n*m-F(c,c-b-1,a,m-1);
}
int main() {
LL a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
printf("%lld\n",F(a,c%a,b,c/a)+c/a+1);
return 0;
}
0%