【【扩展欧几里得】练习题】1 .poj 1061青蛙的约会
最基础的一道
http://poj.org/problem?id=1061
题意：有两只青蛙，一只在坐标x，另一直在坐标y，青蛙x一次跳跃可以前进m单位距离，青蛙y一次跳跃可以前进n单位的距离，两青蛙都在同一纬度，该纬度长度为L。两只青蛙同方向同时跳啊跳，问你最少跳多少次，它们才可以相遇，如果不能相遇，输出impossble
#include
#include
#include
#define max(a,b) a>b?a:b
using namespace std;
#define ll long long
const int maxn = 0x3f3f3f3f;
ll x,y;
ll X,Y,m,n,l;
ll exgcd(ll a,ll b)
{
if(b==0){
x=1;
y=0;
return a;
}
ll d = exgcd(b,a%b);
ll t = x;
x=y;
y=t-(a/b)*y;
return d;
}
int main()
{
while(~scanf("%lld%lld%lld%lld%lld",&X,&Y,&m,&n,&l))
{
ll a,b,c;
a=n-m;
b=l;
c=X-Y;
ll g=exgcd(a,b);
if(c%g){
printf("Impossible\n");
continue;
}
x=x*(c/g);
ll s=b/g;
x=(x%s+s)%s;
printf("%lld\n",x);
}return 0;
} 2.poj 2142 The Balance
http://poj.org/problem?id=2142
题意：一个家伙有一种天平，这种天平只有两种重量的砝码a和b，现在要称出重量为c的物品，问你至少需要多少a和b，答案需要满足a的数量加上b的数量和最小，并且他们的重量和也要最小。（两个盘都可以放砝码）
分析：
求|x|+|y|的最小值。x和y是不定式ax+by==c的解，|x|+|y|==|x0+b/d*t|+|y0-a/d*t|，我们规定a>b
最小值|x|+|y|也一定是在t=y0*d/a附近
#include
#include
#include
#define max(a,b) a>b?a:b
using namespace std;
#define ll long long
const int maxn = 0x3f3f3f3f;
ll abs(ll x){
return x>0?x:-x;
}ll x,y;
ll X,Y,m,n,l;
ll exgcd(ll a,ll b)
{
if(b==0){
x=1;
y=0;
return a;
}
ll d = exgcd(b,a%b);
ll t = x;
x=y;
y=t-(a/b)*y;
return d;
}
int main()
{
ll a,b,c;
while(~scanf("%lld%lld%lld",&a,&b,&c))
{
if(c==0) break;
int flag=0;
if(a #include
#include
#include
#define max(a,b) a>b?a:b
using namespace std;
#define ll long long
const int maxn = 0x3f3f3f3f;
ll abs(ll x){
return x>0?x:-x;
}ll x,y;
ll X,Y,m,n,l;
ll gcd(ll a, ll b)
{
return b==0?a:gcd(b,a%b);
}
void exgcd(ll a, ll b, ll & d, ll &x,ll & y)
{
if(!b){d=a;
x=1;
y=0;
}
else{exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
int main()
{
ll a,b,c;
while(~scanf("%lld%lld%lld",&a,&b,&c))
{
if(c==0) break;
ll x,y,g;
exgcd(a,b,g,x,y);
x=x*(c/g);
y=y*(c/g);
ll s=b/g;
ll x1=(x%s+s)%s;
ll y1=(c-a*x1)/b;
y1=abs(y1);
s=a/g;
y=(y%s+s)%s;
x=(c-b*y)/a;
x=abs(x);
if(x+y>x1+y1)x=x1,y=y1;
printf("%lld %lld\n",x,y);
}
return 0;
}
推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally