题目 : 数论四·扩展欧几里德
描述
小Hi和小Ho周末在公园溜达。公园有一堆围成环形的石板,小Hi和小Ho分别站在不同的石板上。已知石板总共有m块,编号为 0..m-1,小Hi一开始站在s1号石板上,小Ho一开始站在s2号石板上。
小Hi:小Ho,你说我们俩如果从现在开始按照固定的间隔数同时同向移动,我们会不会在某个时间点站在同一块石板上呢?
小Ho:我觉得可能吧,你每次移动v1块,我移动v2块,我们看能不能遇上好了。
小Hi:好啊,那我们试试呗。
一个小时过去了,然而小Hi和小Ho还是没有一次站在同一块石板上。
小Ho:不行了,这样走下去不知道什么时候才汇合。小Hi,你有什么办法算算具体要多久才能汇合么?
小Hi:让我想想啊。。
提示:扩展欧几里德
输入
第1行:每行5个整数s1,s2,v1,v2,m,0≤v1,v2≤m≤1,000,000,000。0≤s1,s2<m
中间过程可能很大,最好使用64位整型
输出
第1行:每行1个整数,表示解,若该组数据无解则输出-1
- 样例输入
-
0 1 1 2 6
- 样例输出
-
5
解法:
先确定5个参数之间关系,建设存在时间t和圈数k满足:
s1+v1*t=s2+v2*t-k*m (v1<v2)
(v1-v2)*t+k*m=(s2-s1)
—————— —— ——————
A B C
看成Ax+By=C,求通解(x,y)使等式成立。使用扩展欧几里得算法。
上式成立的条件是,方程有解,既c为A,B最大公约数的整数倍。
欧几里得算法:是用来求解最大公约数的一种算法,大概思路是gcd(a, b) = gcd(b , a%b),辗转相除法,这样做的好处是算法时间复杂度比枚举大大降低。logn级别。
a%b=0则,a、b的最大公约数为b。
a%b!=0,则gcd(a, b) = gcd(b , a%b)。
通过递归,降低数据的规模,得到一个解。
而扩展欧几里得算法,在欧几里得算法的基础上,再求一组(x,y),ABC均为gcd(A,B)的整数倍,ABC同时缩小gcd(A,B)。
得到A'x+B'y=C',gcd(A',B')=1,A',B'互质(A,B的最大公约数为1)
取2组解
A * x1 + B * y1 = gcd(A, B)
B * x2 + (A % B) * y2 = gcd(B, A % B) 化简为
x1 = y2, y1 = (x2 - ky2)
递归求解(x,y)
终止条件为x=0,y=1;
#include <iostream>
typedef long long LL;
using namespace std; LL gcd(LL a,LL b){
if(b==)
return a;
return gcd(b,a%b);
} LL extend_gcd(LL a, LL b,LL &x,LL &y){
if(a%b!=){
x=;
y=;
return a;
} LL ans=extend_gcd(b,a%b,x,y);
LL temp=x;
x=y;
y=temp-(a/b)*y;
return ans; } int main(){
LL s1,s2,v1,v2,m;
cin>>s1>>s2>>v1>>v2>>m; LL A,B,C,D,x,y; A = v1 - v2;
B = m;
C = s2 - s1; if (A < )
A = A + m ;
D = gcd(A, B); if (C % D)
cout<<-<<endl; A = A / D;
B = B / D;
C = C / D; x = extend_gcd(A, B,x,y);
x = (x * C) % B;
while (x < ){
x = x + B;
}
cout<<x<<endl; }
自己的机器上跑没问题,提交hiho总是WA,伤不起。有大神可以指点一二就好了。