题解 P5171 【Earthquake】

· · 题解

前置知识

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

题意简述

给定 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

其中，大概是这样：

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

\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;
}