UVA - 13250 Balance Game(扩展欧几里得)

Posted on | In , ,

思路

我们要解的一个方程是ax+by+cz=w。显然枚举是O(n^3)会超时，生成函数无法解决x,y,z是负数的情况。注意到m的范围只有5000，所以考虑将方程转化为ax+by=w-cz然后枚举z(-5000,5000)再跑extgcd。由于x*(res/gcds)+k*b/gcds,y*(res/gcds)-k*a/gcds都属于[-m,m]，我们能得到两个k的范围，它们的交集长度的累加就是答案。时间复杂度O(nlogn)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

ll extgcd(ll a,ll b,ll &x,ll &y){
    ll d=a;
    if(b){
        d=extgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
    else{
        x=1,y=0;
    }
    return d;
}
void getBound(ll b,ll g,ll l,ll r,ll &low,ll &high){
    // compute l <= b + g * k <= r, k in [lk, rk]
    if (g > 0) {
		low = ceil((double) (l-b)/g);
		high = floor((double) (r-b)/g);
	} else {
		low = ceil((double) (r-b)/g);
		high = floor((double) (l-b)/g);
	}
}
ll solve(ll a,ll b,ll res,ll n){
    ll x,y;
    ll gcds=extgcd(a,b,x,y);
    if(res%gcds)return 0;
    ll lowa,higha,lowb,highb;
    getBound(x*(res/gcds),b/gcds,-n,n,lowa,higha);
    if(lowa>higha)return 0;
    getBound(y*(res/gcds),-a/gcds,-n,n,lowb,highb);
    if(lowb>highb)return 0;
    lowa=max(lowa,lowb);
    higha=min(higha,highb);
    return higha-lowa+1;
}

int main() {
    ll m,w,n1,n2,n3;
    while(~scanf("%lld%lld",&m,&w)){
        ll ans=0;
        scanf("%lld%lld%lld",&n1,&n2,&n3);
        if(n1<n2)swap(n1,n2);
        if(n1<n3)swap(n1,n3);
        for(ll i=-m;i<=m;i++){
            ll tw=w+i*n1;
            if(tw>=-m*(n2+n3)&&tw<=m*(n2+n3)){
                ans+=solve(n2,n3,tw,m);
            }
        }
        printf("%lld\n",ans);
    }
	return 0;
}