Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
discuss里提到的大多数据都通过,但仍是WA,请教高手//求解模线性方程 #include<iostream> using namespace std; //求a,b最大公约数 //d=ax+by __int64 gy(__int64 a,__int64 b,__int64 &x,__int64 &y) { __int64 d,temp; if(b==0) { x=1; y=0; return a; } d=gy(b,a%b,x,y); temp=x; x=y; y=temp-a/b*y; return d; } //解方程ax=b(mod n) __int64 solv(__int64 a,__int64 b,__int64 n) { __int64 d,x,y; __int64 x0,i,minx=0; d=gy(a,n,x,y); if(b%d==0) { x0=x*(b/d)%n; //x0>=0 or x0<0 if(x0>0) x0=x0-n; //make sure x0<0 minx=x0; for(i=1;i<=d-1;i++) { //解:(x0+i*(n/d)) mod n if((minx=(x0+i*(n/d))%n)>=0) return minx;//只返回最小正数解 } return minx+n;//if minx<0,return minx+n } return -1;//无解 } int main() { __int64 x,y,m,n,l,xx; scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l); // printf("%I64d%I64d%I64d%I64d%I64d\n",x,y,m,n,l); /* * (x+t*m)-(y+t*n)=0 (mod l) that is: t*(m-n)=y-x (mod l) */ if(m>n) xx=solv(m-n,y-x,l); else xx=solv(n-m,x-y,l); if(xx>=0) printf("%I64d\n",xx); else printf("Impossible\n"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator