| ||||||||||
| 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