最近，本人发现了一个新网站poj（不算新）
当然了，上面的资源很好......
就是还没搞清楚它的搜索该怎么弄，如果有大佬能教教我怎么弄，请在下方留言
闲话少说，回归我们的正题
题目转自poj 1061，题目传送门
题目大意：
给你一条线段（头尾相连），给出线段上两点的位置
在给你它们每次移动的距离，让你求出它们在同一个点停下的最短时间
解题思路：
很显然这道题是让你求ax+by=n这个不定方程（a，b已知）
首先，若ax+by=n有整数解，则gcd(a,b)能够整除n
在明确了上面一条之后，我们就要求出ax+by=gcd(a,b)的一组特解(x0,y0)。
那既然这样，我们就要用到数论上的知识了——拓展欧几里得算法
这道题需要用拓欧来解出一组特解
拓欧代码如下：
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==)
{
x=,y=;
return ;
}
exgcd(b,a%b,x,y);
ll tmp=x;
x=y;
y=tmp-(a/b)*y;
}
然后我们把式子两边同时除以gcd(a,b)可得：
cx+dy=1（其中c=a/gcd(a,b)；d=b/gcd(a,b)，很明显c，d互质）
cx+dy=1的通解如下：
x=x0+dt
y=y0+ct t为任意整数
所以，思路就很明了了：
1，拓欧算出特解
2，通过特解算出最小整数解
打个25min应该就应该出来了
AC代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#define ll long long
using namespace std;
ll x,y,n,m,l;
ll a,b,c,d,ss_x,ss_y;
ll gcd(ll a,ll b)
{
if(b==) return a;
else gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==)
{
x=,y=;
return ;
}
exgcd(b,a%b,x,y);
ll tmp=x;
x=y;
y=tmp-(a/b)*y;
}
void init()
{
a=b=c=d=ss_x=ss_y=;
}
int main()
{
while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!=EOF)
{
init();
a=n-m;
b=l;
c=gcd(a,b);
d=x-y;
if(d%c!=) printf("Impossible\n");
else
{
a/=c;
b/=c;
d/=c;
exgcd(a,b,ss_x,ss_y);
ss_x*=d;
ss_x=(ss_x%b+b)%b;
printf("%lld\n",ss_x);
}
}
return ;
}
AC~
特别说明：
接下来，hdu上的题和poj上的题我会交替更新，所以请各位看官不要着急呀~