【poj 1061】青蛙的约会（数论--拓展欧几里德求解同余方程）

题意：已知2只青蛙的起始位置 a,b 和跳跃一次的距离 m,n，现在它们沿着一条长度为 l 的纬线（圈）向相同方向跳跃。问它们何时能相遇？（好有聊的青蛙 (΄◞ิ౪◟ิ‵) *）永不相遇就输出"Impossible"。（蠢得可怜 -_-!）

解法：用拓展欧几里德求同余方程的最小正整数解。(a+mx)-(b+nx)=k*l (k表示圈数) → (m-n)x=k*l+b-a → (m-n)x=b-a(mod l)。当然其实=(b-a)%l 更准确，但反正都是模，也没有关系啦。于是就像上题一样求了。

P.S.代码中有一处加了%p，和没加，时间差别还挺大的......但上一题又不怕......*(￣_￣)*

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6 #define N 2000000000

 7 typedef long long LL;

 8

 9 LL mabs(LL x) {return x>0?x:-x;}

10 LL exgcd(LL a,LL b,LL& x,LL& y)

11 {

12     if (!b) {x=1,y=0; return a;}

13     LL tx,ty,d;

14     d=exgcd(b,a%b,tx,ty);

15     x=ty,y=tx-(a/b)*ty;

16     return d;

17 }

18 int main()

19 {

20     LL aa,bb,m,n,l;

21     scanf("%I64d%I64d%I64d%I64d%I64d",&aa,&bb,&m,&n,&l);

22     LL a,b,c,x,y,p;

23     a=m-n,b=l,c=bb-aa,p=l;

24     LL d=exgcd(a,b,x,y);

25     if (c%d!=0) printf("Impossible\n");

26     else

27     {

28       x=(x*(c/d))%p;//厉害了！删了%p，就从0ms变到16ms了

29       LL t=mabs(b/d);

30       x=(x%t+t)%t;

31       printf("%I64d\n",x);

32     }

33     return 0;

34 }

巴特西

【poj 1061】青蛙的约会（数论--拓展欧几里德求解同余方程）

最新文章

热门文章

巴特西

【poj 1061】青蛙的约会（数论--拓展欧几里德 求解同余方程）

最新文章

热门文章

【poj 1061】青蛙的约会（数论--拓展欧几里德求解同余方程）