UC知道C++ 题，帮忙看看
来源：百度知道 编辑：UC知道 时间：2024/06/07 15:38:09
原题地址http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
#include<iostream>
#include<stdio.h>
using namespace std;
__int64 X=0,Y=0;
__int64 sdf(__int64 len,__int64 L)
{
if(len==0)
{
X=0;Y=1;
return L;
}
__int64 r=sdf(L%len,len);
__int64 e=X;
X=Y-(L/len)*X;
Y=e;
return r;
}
int main()
{
__int64 x,y,m,n,L;
scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L);
__int64 lengh,len;//len距离，len速度差
if(m>n){lengh=(y-x+L)%L;len=m-n;}
else {lengh=(x-y+L)%L;len=n-m;}
__int64 yue=sdf(len,L);//yue最大公约数
if(lengh%yue==0&&m!=n)
{
X*=lengh/yue;
__int64 t=(len*X-lengh)/(L/yue);
if(t<0)t++;//t使X步len后大于lengh
printf("%I64d\n",X-t*(L/yue));
}
else cout<<"Impos
#include<iostream>
#include<stdio.h>
using namespace std;
__int64 X=0,Y=0;
__int64 sdf(__int64 len,__int64 L)
{
if(len==0)
{
X=0;Y=1;
return L;
}
__int64 r=sdf(L%len,len);
__int64 e=X;
X=Y-(L/len)*X;
Y=e;
return r;
}
int main()
{
__int64 x,y,m,n,L;
scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L);
__int64 lengh,len;//len距离，len速度差
if(m>n){lengh=(y-x+L)%L;len=m-n;}
else {lengh=(x-y+L)%L;len=n-m;}
__int64 yue=sdf(len,L);//yue最大公约数
if(lengh%yue==0&&m!=n)
{
X*=lengh/yue;
__int64 t=(len*X-lengh)/(L/yue);
if(t<0)t++;//t使X步len后大于lengh
printf("%I64d\n",X-t*(L/yue));
}
else cout<<"Impos
我也贴贴代码
用的是扩展 欧几里德算法
# include <iostream>
using namespace std;
typedef long long llong;
llong Extended_Euclid(llong m,llong n,llong &x,llong &y)
/* 返回的 d 满足 d = gcd(m,n) = mx+ny */
{
llong x0,y0,x1,y1,r,k;
x0=1;y0=0;x1=0;y1=1;
r=(m%n+n)%n;
k=(m-r)/n;
x=0;y=1;
while(r)
{
x=x0-k*x1;y=y0-k*y1;
x0=x1;y0=y1;
x1=x;y1=y;
m=n;n=r;r=m%n;
k=(m-r)/n;
}
return n;
}
int main()
{
llong x,y,m,n,l,u,v,pp,k,temp;
cin>>x>>y>>m>>n>>l;
if(x<y) {temp=x;x=y;y=temp;temp=m;m=n;n=temp;}
pp=Extended_Euclid(n-m,l,u,v);
k=l/pp;
if((x-y)%pp||m==n)
cout<<"Impossible"<<endl;
else{
u=u*((x-y)/pp);
u=(u%k+k)%k;
cout<<u<<endl;
}
return 0;
}