http://poj.org/problem?id=3863
题意：一栋大楼有无数层，每个电梯有两个开关，选择向上ui层，向下di层，问一共按n次开关最低能到达第几层，起点为第0层，如果坐在的层数小于di不能往下走。
扩展欧几里德：
通过这个题对扩展欧几里得又有了新的认识：首先设向上按x次，向下按y次,能到达的最低层数为z.则得到(1) ui*x - di*y = z; (2) x + y = n;联合(1),(2)得：-z + (ui + di)*x = n*di;
转化一下得到 a*x + b*y = p 形式的式子，于是就可以利用扩展欧几里得求x的最小正整数值即可。 但是必须注意的是：在利用扩展欧几里得求解时，要求的a,b必须是非负数，这里a是负数了，所以要处理一下，在利用扩展欧几里德求解时将a = -a;置为正数，把负数加大x上面，于是我们求解出的x事最大的负数，只要将其取反就是最小的正整数了。
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 107
#define LL long long
using namespace std;
LL exp_gcd(LL a,LL b,LL &x,LL &y)
{if (b == 0){x = 1; y = 0;return a;}LL d = exp_gcd(b,a%b,x,y);LL tmp = x;x = y; y = tmp - (a/b)*y;return d;
}int main()
{int ui,di,n,m;scanf("%d%d",&n,&m);LL ans = 999999999;for (int i = 0; i < m; ++i){scanf("%d%d",&ui,&di);LL a = 1;//置为正数LL b =(ui + di);LL p = n*di;LL x,y;LL d = exp_gcd(a,b,x,y);if (p%d == 0){p /= d;a /= d;b /= d;x*=p;x = (x%b + b)%b;while (x >= 0) x -= b;//求出最大分数x = -x;if (ans > x) ans = x;}}printf("%lld\n",ans);return 0;
}
二分：
二分枚举向上的次数，只要将ui*x - di*y = z 尽量缩小就好了。 注意z>=0
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 107
#define LL long long
using namespace std;int ui,di,n,m;
int bsearch(int l,int r)
{int sum = 0;int mid = 0;while (l <= r){mid = (l + r)>>1;sum = ui*mid - di*(n - mid);if (sum > 0) r = mid - 1;else l = mid + 1;}return ui*l - di*(n - l);//枚举最低的层数
}
int main()
{scanf("%d%d",&n,&m);int ans = 999999999;for (int i = 0; i < m; ++i){scanf("%d%d",&ui,&di);int sum = bsearch(0,n);//printf("%d\n",sum);if (ans > sum) ans = sum;}printf("%d\n",ans);return 0;
}
