BZOJ2987 Earthquake <类欧几里得>

Problem

Earthquake

Description

给定，求满足方程的非负整数解的个数。

Input

输入一行三个整数，含义如上所述。

Output

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

Sample Input

3 4 13

Sample Output

12

HINT

标签：类欧几里得

Solution

类欧几里得基础题。

令，则根据的关系将其分为两类递归处理

• 若，则将、分离常数后可知
• 若，则

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

Code

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