BZOJ2987 Earthquake <类欧几里得>

Posted on Symbols count in article: 470 Reading time ≈ 2 mins.

Problem

Earthquake

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

给定A,B,CA,B,C，求满足方程Ax+By≤CAx+By\le C的非负整数解的个数。

Input

输入一行三个整数A,B,CA,B,C，含义如上所述。

Output

输出一行一个整数，表示非负整数解的个数。

Sample Input

1
3 4 13

Sample Output

1
12

HINT

A,B≤109,C≤min⁡(A,B)×109A,B\le10^9,C\le\min(A,B)\times10^9

标签：类欧几里得

Solution

类欧几里得基础题。

令f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor，则根据a,b,ca,b,c的关系将其分为两类递归处理

  • 若a≥c或b≥ca\ge c或b\ge c，则将ac\frac{a}{c}、bc\frac{b}{c}分离常数后可知$$f(a,b,c,n)=\frac{\lfloor\frac{a}{c}\rfloor\cdot n\cdot(n+1)}{2}+\lfloor\frac{b}{c}\rfloor\cdot(n+1)+f(a%c,b%c,c,n)$$
  • 若a<c且b<ca<c且b<c，则

f(a,b,c,n)=∑i=0n∑j=0m−1[⌊ai+bc⌋≥j+1]=∑i=0n∑j=0m−1[ai≥cj+c−b]=∑i=0n∑j=0m−1[i≥⌈cj+c−ba⌉]=∑i=0n∑j=0m−1[i>⌊cj+c−b−1a⌋]=∑j=0m−1(n−⌊cj+c−b−1a⌋)=nm−f(c,c−b−1,a,m−1)\begin{aligned} f(a,b,c,n) &=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[\lfloor\frac{ai+b}{c}\rfloor\ge j+1]\\ &=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[ai\ge cj+c-b]\\ &=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[i\ge\lceil\frac{cj+c-b}{a}\rceil]\\ &=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[i>\lfloor\frac{cj+c-b-1}{a}\rfloor]\\ &=\sum_{j=0}^{m-1}(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)\\ &=nm-f(c,c-b-1,a,m-1)\\ \end{aligned}

由于每次均将参数变为其辗转相模的结果，故而复杂度和欧几里得算法大致相同。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt f(lnt a, lnt b, lnt c, lnt n) {
    if (!c) return 0;
    if (a >= c || b >= c)
        return a/c*n*(n+1)/2+b/c*(n+1)+f(a%c, b%c, c, n);
    return (a*n+b)/c*n-f(c, c-b-1, a, (a*n+b)/c-1);
}
int main() {
    lnt a, b, c; read(a), read(b), read(c);
    return printf("%lld\n", f(a, c%a, b, c/a)+c/a+1), 0;
}