「Luogu 5171」Earthquake

发表于 | | 阅读次数:
字数统计: 503 字

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%