http://poj.org/problem?id=1061刚刚学了点数论,也好几天没有写代码了,生疏了不少,总是有错误,编译个程序怎么都那么纠结啊,看来水平实在是差啊!!
线性同余,方程还是很好就构造出来了,extended_euclid,中国剩余定理,可是后面却不指导怎么求最小的整数了:
看了看大牛的题解,原来这样啊,自己数论还得多学学才行,多想想啊:
分析:设青蛙跳了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;
}
总结:代码,还是得天天写,三日不练手生。自己多想想,多思考思考才能提升能力哈。
不要总是去看别人的题解,要有自己的思路哈。
数论,还得继续看,继续学。要吃透才行。