| ||||||||||
| 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 | |||||||||
第一次扩展欧几里得 oms AC#include<stdio.h>
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
void extend_gcd(int a,int b,__int64 &x,__int64 &y)
{
if(b==0)
{
x=1;
y=0;
return ;
}
else
{
extend_gcd(b,a%b,x,y);
__int64 temp=x;
x=y;
y=temp-a/b*y;
}
}
int main (void)
{
int x,y,m,n,l;
__int64 x1,y1;
int a,b,c;
int temp;
while(scanf("%d %d %d %d %d",&x,&y,&m,&n,&l)!=EOF)
{
a=m-n;
b=l;
temp=b;
c=y-x;
int r=gcd(a,b);
// printf("%d\n",r);
if(c%r)
printf("Impossible\n");
else
{
extend_gcd(a,b,x1,y1);
// printf("%d\n",r);
// printf("%d %d %d %d %d\n",a,b,c,x1,y1);
__int64 t=(c*x1/r)/b;
x1=c*x1/r-b*t;
if(x1<0)
x1+=b;
printf("%I64d\n",x1);
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator