| ||||||||||
| 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 | |||||||||
Re:测试数据是不是错了?In Reply To:Re:测试数据是不是错了? Posted by:encapsulation at 2006-02-05 15:44:27 #include <math.h>
#include <stdio.h>
int gcd(int a,int b)
{
int x=1;
int y=1;
if (b>a)
{
x=b;
y=a;
}
else
{
x=a;
y=b;
}
while (y)
{
a=y;
y=x%y;
x=a;
}
return x;
}
int fun(int a,int b)
{
int temp=1;
int Q0=1;
int Q1=0;
int Q2=1;
int q=0;
int count=0;
while (b!=1)
{
q=a/b;
temp=a;
Q2=q*Q1+Q0;
a=b;
b=temp%b;
count++;
Q0=Q1;
Q1=Q2;
}
if (count%2==0)
Q2=-Q2;
return Q2;
}
void main()
{
int m=0;
int n=0;
int x=0;
int y=0;
int L=0;
int temp=0;
int nGcd=1;
scanf("%d%d%d%d%d",&x,&y,&m,&n,&L);
if (m==n)
{
printf("Impossible\n");
return;
}
nGcd=gcd((int)abs(m-n),L);
if ( ((int)abs(x-y))%nGcd!=0 )
{
printf("Impossible\n");
return;
}
if (m-n>0)
{
L/=nGcd;
x=(y-x)/nGcd;
m=(m-n)/nGcd;
temp=fun(m,L);
temp*=x;
while (temp<0)
temp+=L;
if (temp>0)
{
while (temp>0)
temp-=L;
temp+=L;
}
}
else if (m-n<0)
{
L/=nGcd;
x=(x-y)/nGcd;
m=(n-m)/nGcd;
temp=fun(m,L);
temp*=x;
while (temp<0)
temp+=L;
if (temp>0)
{
while (temp>0)
temp-=L;
temp+=L;
}
}
printf("%d\n",temp);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator