http://poj.org/problem?id=1061剛剛學了點數論，也好幾天沒有寫代碼了，生疏了不少，總是有錯誤，編譯個程序怎么都那么糾結啊，看來水平實在是差啊??！
線性同余，方程還是很好就構造出來了，extended_euclid，中國剩余定理，可是后面卻不指導怎么求最小的整數了：
看了看大牛的題解，原來這樣啊，自己數論還得多學學才行，多想想?。?br />
分析:設青蛙跳了k次,那么就有(x+mk)-(y+nk)=p*L.
即x-y+(m-n)k=p*L,即(m-n)*k≡(y-x) (mod L).
這個線性同余方程有解當且僅當gcd(m-n,L)|(y-x).
令a=m-n,b=L,c=y-x.用擴展歐幾里得解方程ax+by=c.
可以求出原方程的一個解.如何求最小正整數解呢?
假設我們已經得到一個x0,令d=gcd(m-n,L),
那么所有解可以表示為x=x0+k*L/d.
設L'=L/d.
Xmin=(x0 mod L'+L') mod L'.
WA兩次，0Ms，囧，還有一次編譯錯誤?。?！
#include<stdio.h>
#include<string.h>
#include<math.h>
long long c,d;
long long gcd_ext(long long a,long long b)
{
long long gcd,t;
if (!b)
{
c=1;d=0;
return a;
}
gcd=gcd_ext(b,a%b);
t=c;c=d;d=t-a/b*d;
return gcd;
}
int main()
{
long long x,y,m,n,L,a,b,gcd;
while (scanf("%I64d%I64d",&x,&y)==2)
{
scanf("%I64d%I64d%I64d",&m,&n,&L);
a=m>n?m-n:n-m;
b=m>n?y-x:x-y;
gcd=gcd_ext(a,L);
L=L/gcd;
if (b%gcd==0)
printf("%I64d\n",((c*b/gcd)%L+L)%L);
else
printf("Impossible\n");
}
return 0;
}
總結：代碼，還是得天天寫，三日不練手生。自己多想想，多思考思考才能提升能力哈。
不要總是去看別人的題解，要有自己的思路哈。
數論，還得繼續看，繼續學。要吃透才行。