题解 - Vijos

4

PowderHan LV 10 @ 2017-05-07 12:44:41

/*
根据题意不难得出 Mt+x-nt-y=pl.即(m-n)t-pl=y-x
令a=m-n, b=l ,c=y-x ,x=t ,y=-p
所以本题是求一个不定方程(ax+by=c）的最小非负x
可以用扩展欧几里德`所谓扩展欧几里得就是我们用欧几里得(a,b)=(b,a MOD b)求最大公约数的同时求出ax+by=(a,b)的一组特解.x0,y0
令d=(a,b).若c mod d<>0则 Impssible
否则x0*c/d,y0*c/d为ax+by=c的一组特解
所以通解为x0*c/d+b/d*t,y0*c/d-a/d*t
现在剩下的问题就是如何用扩欧求ax+by=(a,b)的一组特解
方法如下：
设ax0+by0=(a,b)=(b,a mod b)=bx1+(a mod b)y1 （*）
而a mod b=a-[a/b]代入（*）式比较系数得x0=y1,y0=x1-y1*[a/b]
所以我们可以递归实现以上算法.
最后还要注意几个个细节.
1.a,b,c若是负数的话.虽然欧几里得MS可以处理.但是mod 运算会变得很别扭.所以为了变成容易实现.建议将a.b.c转换为正数再解.
对于a我们可以讨论m>n,n<m两种情况.而b本身就是正的.对于c可以加b加到非负为止
即 ax+by=c 方程两边同时加q倍的b解不变
2.中间结果有可能超出longint。。最好用int64.虽然NOIP已经不让用了.
这样这个题就解决了。
根据同余方程的ax+by=c，可以得出a=n-m,b=l,c=x-y 之后扩展欧几里得求线性同余方程。
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

long long x,y,m,n,l;

void gcd(long long a,long long b,long long& d,long long & x,long long& y)
{
    if(!b)  {d=a;x=1;y=0;}
    else    {gcd(b,a%b,d,y,x);   y-=x*(a/b);}
}

int main()
{
    cin>>x>>y>>m>>n>>l;
    long long a=((n-m)%l+l)%l;  long long b=l;    long long c=((x-y)%l+l)%l;
    long long d;
    gcd(a,b,d,x,y);
    if(c%d)
        cout<<"Impossible"<<endl;
    else
    {
        long long a1=x*(c/d);
        long long a2=abs(l/d);
        while(a1<0)
            a1+=a2;
        while(a1-a2>=0)
            a1-=a2;
        cout<<a1<<endl;
    }
    return 0;
}

1

夜空中的云鲸 LV 6 @ 2022-08-13 12:10:01

代码飞来！

#include<bits/stdc++.h>
using namespace std;
long long x,y,m,n,l;
void gcd(long long a,long long b,long long& d,long long & x,long long& y){
    if(!b)  {d=a;x=1;y=0;}
    else    {gcd(b,a%b,d,y,x);   y-=x*(a/b);}
}
int main(){
    cin>>x>>y>>m>>n>>l;
    long long a=((n-m)%l+l)%l;  long long b=l;    long long c=((x-y)%l+l)%l;
    long long d;
    gcd(a,b,d,x,y);
    if(c%d)
        cout<<"Impossible"<<endl;
    else{
        long long a1=x*(c/d);
        long long a2=abs(l/d);
        while(a1<0)
            a1+=a2;
        while(a1-a2>=0)
            a1-=a2;
        cout<<a1<<endl;
    }
    return 0;
}

1

littleseven (littleseven) LV 7 @ 2019-04-28 18:42:23

解法拓展欧几里得（exgcd），差不多裸题吧
有几个坑点：
1.一定要判断n,m大小并修改a,b的值（具体看代码）
2.不要忘记有“Impossible”情况
3.拓展GCD最小整数解问题
4.本题数据需要longlong
下面上代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
LL x,y;
LL s1,s2,m,n,l;
LL exgcd(LL a,LL b)
{
    if(b==0) {x=1,y=0;return a;}
    LL t=exgcd(b,a%b);
    LL temp=x; x=y;
    y=temp-a/b*y;
    return t;
}
int main()
{
    cin>>s1>>s2>>m>>n>>l;
    LL a=n-m,b=s1-s2;
    if(a<0) b=-b,a=-a;
    LL ans=exgcd(a,l);
    if(b%ans!=0) cout<<"Impossible"<<endl;
    else cout<<((x*(b/ans))%(l/ans)+(l/ans))%(l/ans);
    return 0;
}

1

gsrq LV 10 @ 2009-07-25 17:41:55

var temp,n,m,x,y,l,c,d,a,b:int64;

function gcd(a,b:int64;var x,y:int64):int64;

var x1,y1:int64;

begin

if a mod b=0 then begin gcd:=b;x:=0;y:=1;exit;end;

x1:=0;y1:=0;

gcd:=gcd(b,a mod b,x1,y1);

x:=y1;

y:=x1-y1*(a div b);

end;

begin

readln(x,y,m,n,l);

if(m=n)and((x-y)mod l0)then begin writeln('Impossible');halt;end;

if m>n then begin a:=m-n;b:=l;c:=((y-x)mod l+l)mod l;end;

if n>m then begin a:=n-m;b:=l;c:=((x-y)mod l+l)mod l;end;

d:=gcd(a,b,x,y);x:=x*c div d;

if c mod d0 then begin writeln('Impossible');halt;end;b:=b div d;

x:=(x mod b+b)mod b;

writeln(x);

end.

0

最强王者 LV 8 @ 2021-11-11 12:47:20

这是我的第一篇题解，请大家多多关照。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

long long x,y,m,n,l;

void gcd(long long a,long long b,long long& d,long long & x,long long& y)
{
if(!b) {d=a;x=1;y=0;}
else {gcd(b,a%b,d,y,x); y-=x*(a/b);}
}

int main()
{
cin>>x>>y>>m>>n>>l;
long long a=((n-m)%l+l)%l; long long b=l; long long c=((x-y)%l+l)%l;
long long d;
gcd(a,b,d,x,y);
if(c%d)
cout<<"Impossible"<<endl;
else
{
long long a1=x*(c/d);
long long a2=abs(l/d);
while(a1<0)
a1+=a2;
while(a1-a2>=0)
a1-=a2;
cout<<a1<<endl;
}
return 0;
}

0

腿毛飘逸蒟蒻 LV 6 @ 2021-08-18 18:39:30

x+tm=y+tn (mod l)
(m-n)t-kl=y-x
所以可以用 exgcd 来求解，然后是一些小细节


#include<iostream>
#include<cstdio>
#define ll long long 
using namespace std;
ll ans,x1,y1;

ll exgcd(ll a,ll b,ll &x1, ll &y1)
{
    if(!b)
    {
        x1=1;
        y1=0;
        return a;
    }
    ans=exgcd(b,a%b,x1,y1);
    ll t=x1;
    x1=y1;
    y1=t-a/b*y1;
    return ans;
}

int main()
{
    ll n,m,x,y,l;
    cin>>x>>y>>m>>n>>l;
    ll b=n-m,a=x-y;
    if(b<0)
    {
        b=-b;
        a=-a;
    }//处理负数 
    exgcd(b,l,x1,y1);
    if(a%ans!=0)//判断方程有无解。 
        cout<<"Impossible";
    else
        cout<<((x1*(a/ans))%(l/ans)+(l/ans))%(l/ans);//处理负数 
}

0

涅槃、卿莫 (龙阿紫) LV 10 @ 2021-07-23 08:59:54

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

long long x,y,m,n,l;

void gcd(long long a,long long b,long long& d,long long & x,long long& y)
{
if(!b) {d=a;x=1;y=0;}
else {gcd(b,a%b,d,y,x); y-=x*(a/b);}
}

int main()
{
cin>>x>>y>>m>>n>>l;
long long a=((n-m)%l+l)%l; long long b=l; long long c=((x-y)%l+l)%l;
long long d;
gcd(a,b,d,x,y);
if(c%d)
cout<<"Impossible"<<endl;
else
{
long long a1=x*(c/d);
long long a2=abs(l/d);
while(a1<0)
a1+=a2;
while(a1-a2>=0)
a1-=a2;
cout<<a1<<endl;
}
return 0;
}

0

C20191629 LV 7 @ 2017-07-20 15:45:32

青蛙的约会不解释……
exgcd就可以了（话说这不是模板题吗）

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
ll x,y,n,m,L;
void kzgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(b==0)
    {
        d=a;x=1;y=0;
        return;
    }
    kzgcd(b,a%b,d,y,x);
    y-=a/b*x;
}
int main()
{
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
    ll a=((n-m)%L+L)%L;
    ll b=L;
    ll c=((x-y)%L+L)%L;
    ll d,e,p,q;
    kzgcd(a,b,d,p,q);
    if(c%d)
    {
        printf("Impossible");
        return 0;
    }
    e=b/d;
    printf("%lld",((p*(c/d))%e+e)%e);
}

0

mrkrnblsa LV 8 @ 2017-06-09 13:53:55

蛤蛤蛤蛤蛤蛤第100条题解！！！
只要exgcd求就行了，但同余式右方不是1而是两地的距离之差，编程要考虑到这点，否则。。。你懂得。。。
另外，用longlong，否则。。。你还是懂的。。。
#include<stdio.h>
using namespace std;
long long x,y,m,n,l,g,r,rr;
void exgcd(long long d,long long f){
if(!f){x=1,y=0,g=d;return;}
exgcd(f,d%f);
r=x,x=y,y=r-d/f*y;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("cuo.txt","w",stdout);
scanf("%d%d%d%d%d",&x,&y,&m,&n,&l);
n%=l,m%=l;
if(m<=n)
rr=(x-y+l)%l,exgcd(n-m,l);
else
rr=(y-x+l)%l,exgcd(m-n,l);
// rr=(y-x+l)%l,exgcd((m-n+l)%l,l);
if(!(rr%g)){rr=rr/g*x,rr%=l/g;if(rr<0)rr+=l/g;printf("%lld",rr);}
else puts("Impossible");
// printf("x=%d y=%d m=%d n=%d l=%d g=%d",x,y,m,n,l,g);
// fclose(stdin);
// fclose(stdout);
return 0;
}

0

芙兰朵露•斯卡雷特 LV 8 @ 2016-07-09 15:26:49

#include <iostream>
using namespace std;
typedef long long Long;
inline Long abs(Long l) {
    return l<0?-l:l;
}
Long x0, y0;
Long x,y,m,n,L;
Long gcd(Long a, Long b) {
    Long t, d;
    if (b == 0) {
        x0 = 1;
        y0 = 0;
        return a;
    }
    d = gcd(b, a % b);
    t = x0;
    x0 = y0;
    y0 = t - a / b * y0;
    return d;
}
int main(int argc,char*argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>x>>y>>m>>n>>L;
    x=x%L,y=y%L;
    if(x>y) {
        Long t = y;
        y = x,x = t,t = n,n = m,m = t;
    }
    Long a = abs(m - n);
    Long b = -L;
    Long c;
    if (m > n)
        c = y - x;
    else
        c = x - y + L;
    Long d = gcd(a, b);
    if (c % d != 0)
        cout<<"Impossible\n";
    else {
        Long add1 = x0 * c / d;
        Long add2 = abs(b / d);
        while (add1 < 0)
            add1 += add2;
        while (add1 - add2 >= 0)
            add1 -= add2;
        cout<<add1<<"\n";
    }
    return 0;
}

0

ljlovest LV 9 @ 2009-10-26 19:55:55

这道题为什么要用ax+by=c呢，追及1圈肯定有交点，为什么一定要整数天

HBat @ 2015-10-25 16:17:24

他们出题从来不考虑实际情况

0

richardwsy LV 8 @ 2009-08-18 23:26:29

裴蜀等式+一次不定方程构造小数学

0

叶德铭 LV 9 @ 2009-08-04 15:21:16

pku青蛙的约会

0

1s LV 10 @ 2009-08-03 17:57:36

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

0

董 LV 10 @ 2009-07-31 13:09:16

http://hi.baidu.com/%CB%D5%CC%DAsauterne

0

zjaylucifer LV 8 @ 2009-07-31 09:00:22

哇哈哈！！！第600人。。。

Flag 　　 Accepted

题号　　P1009

类型(?) 　　数论 / 数值

通过　　600人

0

qzs123 LV 8 @ 2009-07-22 18:15:16

“与此同时，出众的他也被世界各国遣清使臣所折服”

?????

这句话有语病。

0

ayqzwu110 LV 7 @ 2009-07-20 11:35:15

Program P1009;

var

x,y,m,n,l,v,s,t,k,a:int64;

Function gcd(a,b:int64):int64;

var

p:int64;

begin

while b>0 do

begin

p:=a mod b;

a:=b;

b:=p;

end;

exit(a);

end;

Function Find(a,b:int64):int64;

var

x,y,c:array [1..32] of int64;

m,i:longint;

p:int64;

begin

fillchar(x,sizeof(x),0);

fillchar(y,sizeof(y),0);

fillchar(c,sizeof(c),0);

m:=0;

while b>0 do

begin

inc(m);

c[m]:=a div b;

p:=a mod b;

a:=b;

b:=p;

end;

x[m+1]:=1;

y[m+1]:=0;

for i:=m downto 1 do

begin

x[i]:=y;

y[i]:=x-c[i]*y;

end;

exit(x[1]);

end;

begin

readln(x,y,m,n,l);

while x

0

gongyaoheng1 LV 3 @ 2009-07-20 11:18:05

program aa;

var xx,yy,m,n,l,d,ans,t,tt,p,x,y,ttt:int64;

function egcd(a,b:int64;var x,y:int64):int64;

begin

if b=0 then

　　begin

　　 egcd:=a;

　　 d:=a;

　　 x:=1;

　　 y:=0;

　　end

else

　　begin

　　 egcd(b,a mod b,x,y);

　　 t:=x;//x'

　　 x:=y;//y'

　　 y:=t-(a div b)*x;

　　end;

end;

begin

readln(xx,yy,m,n,l);

ans:=-1;

tt:=(yy-xx) mod l;

egcd(m-n,l,x,y);

if (tt mod d0) then begin writeln('Impossible'); halt;end;

x:=x*(tt div d);

x:=x-(x div l)*l;

while x0 do x:=x-l;

writeln(x);

end.

0

cody332400 LV 7 @ 2009-07-18 21:39:58

这个题目对我有难度，有哪位好心的大哥大姐能帮帮我啊

题解

110 条题解

清帝之惑之康熙

信息

状态

开发

支持

题解

110 条题解

清帝之惑之康熙

信息

状态

开发

支持

还没有账户？

登录