http://poj.org/problem?id=1061剛剛學(xué)了點(diǎn)數(shù)論，也好幾天沒(méi)有寫(xiě)代碼了，生疏了不少，總是有錯(cuò)誤，編譯個(gè)程序怎么都那么糾結(jié)啊，看來(lái)水平實(shí)在是差啊！！
線(xiàn)性同余，方程還是很好就構(gòu)造出來(lái)了，extended_euclid，中國(guó)剩余定理，可是后面卻不指導(dǎo)怎么求最小的整數(shù)了：
看了看大牛的題解，原來(lái)這樣啊，自己數(shù)論還得多學(xué)學(xué)才行，多想想?。?br />
分析:設(shè)青蛙跳了k次,那么就有(x+mk)-(y+nk)=p*L.
即x-y+(m-n)k=p*L,即(m-n)*k≡(y-x) (mod L).
這個(gè)線(xiàn)性同余方程有解當(dāng)且僅當(dāng)gcd(m-n,L)|(y-x).
令a=m-n,b=L,c=y-x.用擴(kuò)展歐幾里得解方程ax+by=c.
可以求出原方程的一個(gè)解.如何求最小正整數(shù)解呢?
假設(shè)我們已經(jīng)得到一個(gè)x0,令d=gcd(m-n,L),
那么所有解可以表示為x=x0+k*L/d.
設(shè)L'=L/d.
Xmin=(x0 mod L'+L') mod L'.
WA兩次，0Ms，囧，還有一次編譯錯(cuò)誤?。?！
#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;
}
總結(jié)：代碼，還是得天天寫(xiě)，三日不練手生。自己多想想，多思考思考才能提升能力哈。
不要總是去看別人的題解，要有自己的思路哈。
數(shù)論，還得繼續(xù)看，繼續(xù)學(xué)。要吃透才行。