【BZOJ2987】类欧几里得算法

刚学习了类欧算法(除了时间复杂度,和欧算一点关系都没有orz),还没来得及肝先知和圣骑士。

2987: Earthquake

Time Limit: 10 Sec Memory Limit: 128 MB Submit: 283 Solved: 161 [Submit][Status][Discuss]

Description

给定a,b,c,求满足方程Ax+By<=C的非负整数解

A,B<=10^9.C<=Min(A,B)*10^9

Input

Output

Sample Input

3 4 13

Sample Output

12

移项得到 y \le \frac{c-a*x}{b} 啥,有负数形式,显然不棒 那么我们转换一下变成了 y \le \frac{a*x+c%b}{b} x可以从0枚举到c/a,这样就很像类欧里面的形式 \sum_{i=0}^n \lfloor \frac{a*i+b}{c} \rfloor 直接套用就可以了,具体可以见luogu模板题题解

#include<bits/stdc++.h>
typedef long long ll;

using namespace std;

ll a,b,c;

ll F(ll a,ll b,ll c,ll n) {
    if(!c) return 0;
    if(!a) return 1ll*(n+1)*(b/c);
    if(a>=c||b>=c) return 1ll*n*(n+1)/2*(a/c)+(n+1)*(b/c)+F(a%c,b%c,c,n);
    return n*((a*n+b)/c)-F(c,c-b-1,a,(a*n+b)/c-1);
}

int main() {
    scanf("%lld%lld%lld",&a,&b,&c);
    printf("%lld\n",F(a,c%a,b,c/a)+c/a+1);
}
Last modification:June 2nd, 2019 at 06:43 pm

Leave a Comment