| ||||||||||
| 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 | |||||||||
没道理的事啊~1061我用了数论的解不定方程的方法怎么就是做不出来的呢?
什么原因呢
#include<iostream.h>
#define DS_N 0
#define DS_P 1
typedef struct
{
long x;
long y;
} ANSWER;
long gcd(long a,long b)
{
if(a%b==0)
return b;
if(b%a==0)
return a;
return a>b?gcd(a%b,b):gcd(a,b%a);
}
ANSWER exgcd(long a,long b)
{
ANSWER rst,buf;
if(a==1)
{
rst.x=1;
rst.y=0;
return rst;
}
if(b==1)
{
rst.x=0;
rst.y=1;
return rst;
}
if(a>b)
{
buf=exgcd(a%b,b);
rst.y = buf.y-(a/b)*buf.x;
rst.x = buf.x;
return rst;
}
else
{
buf =exgcd(a,b%a);
rst.x =buf.x-(b/a)*buf.y;
rst.y =buf.y;
return rst;
}
}
main()
{
long sa,sb,va,vb,l;
long ds,dv,times;
short statu=0;
long a,b,c1;
long b1;
long g;
cin>>sa>>sb>>va>>vb>>l;
if(va>vb)
{
dv=vb-va;
ds=sb-sa;
}
else if(va==vb)
{
cout<<"Impossible";
return 0;
}
else
{
dv=va-vb;
ds=sa-sb;
}
if(ds>=0)
statu=DS_P;
else
{
statu=DS_N;
ds=-ds;
}
g=gcd(-dv,l);
if(ds%g!=0)
{
cout<<"Impossible";
return 0;
}
a=(-dv)/g;
b=l/g;
c1=ds/g;
ANSWER rst=exgcd(a,b);
rst.x *= c1;
rst.y *= c1;
if(statu==DS_P)
{
if(rst.x>0)
times=rst.x%b;
else times=rst.x%b+b;
}
else
{
if(rst.x>0)
times=-(rst.x%b-b);
else times=-rst.x%b;
}
cout<<times;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator