最近, 本人发现了一个新网站 poj http://poj.org/ (不算新)
当然了, 上面的资源很好......
就是还没搞清楚它的搜索该怎么弄, 如果有大佬能教教我怎么弄, 请在下方留言
闲话少说, 回归我们的正题
题目转自 poj 1061, 题目传送门 http://poj.org/problem?id=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==0)
- {
- x=1,y=0;
- 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==0) return a;
- else gcd(b,a%b);
- }
- void exgcd(ll a,ll b,ll &x,ll &y)
- {
- if(b==0)
- {
- x=1,y=0;
- 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=0;
- }
- 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!=0) 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 0;
- }
- AC~
特别说明:
接下来, hdu 上的题和 poj 上的题我会交替更新, 所以请各位看官不要着急呀~
来源: http://www.bubuko.com/infodetail-3323215.html