题解：P5171 Earthquake

· · 题解

题意简述

求解 ax+by \le c 的非负整数解个数。其中 1 \le a,b \le 10^9。

做法简析

看到这个式子很容易想到扩展欧几里德与二元一次不定方程，于是我们用它们的远房亲戚类欧几里得算法解决问题。

我们先推式子：

ax+by \le c \iff x \le \lfloor \frac{c-by}{a} \rfloor

考虑对 y 求和，那么答案就是：

\sum_{y=0}^{\lfloor \frac{c}{b} \rfloor} (\lfloor \frac{c-by}{a} \rfloor+1)

这已经很接近类欧的形式了，但是斜率是负的不好做。我们考虑引入一个辅助项调整斜率：

\sum_{y=0}^{\lfloor \frac{c}{b} \rfloor} (\lfloor \frac{c+(a-1)by}{a} \rfloor - by +1)

然后直接类欧一下就好了。

code

#include<bits/stdc++.h> 
#define int long long
using namespace std;
int solve(int a,int b,int c,int n){
    if(!n) return b/c;
    if(!a) return b/c*(n+1);
    if(a>=c || b>=c){
        return solve(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-solve(c,c-b-1,a,m-1);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    int ans=solve((a-1)*b,c,a,c/b);
    ans-=b*(c/b)*(c/b+1)/2;
    cout<<ans+c/b+1;
}

关于类欧的推导

对于求和式 \sum_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor，我们分两类讨论：

\sum_{i=0}^{n} \lfloor \frac{(a \bmod c)i+(b \bmod c)}{c} \rfloor + \frac{\lfloor \frac{a}{c} \rfloor (n) (n+1)}{2} + {\lfloor \frac{b}{c} \rfloor(n+1)}

对于后一种情况，原式的意义是对每个 i 计数 y \le \lfloor \frac{ai+b}{c} \rfloor，我们变形为 i \ge \lceil \frac{cy-b}{a} \rceil = \lfloor \frac{cy+a-b-1}{a} \rfloor。

之后，求和式变为：

\sum_{y=1}^{m} n-\lfloor \frac{cy+a-b-1}{a} \rfloor+1 = m(n+1) - \sum_{y=1}^{m} \lfloor \frac{cy+a-b-1}{a} \rfloor

其中 m=\lfloor \frac{cn+a-b-1}{a} \rfloor。

我们考虑将求和范围统一为从 0 开始。原式变为：

mn - \sum_{y=0}^{m-1} \lfloor \frac{cy+c-b-1}{a} \rfloor

这样，我们反复应用两种基本情形。因为这种操作很像辗转相除的过程，因此这被称为类欧几里得算法。时间复杂度可以证明为 \log 级别的。