var
x,y,a,b,d:int64;

procedure gcd(a,b:int64);
var
t:int64;
begin
if (a mod b=0) then
begin
x:=0;
y:=1;
end
else
begin
gcd(b,a mod b);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
end;

begin
readln(a,b);
d:=b;
gcd(a,b);
writeln((x mod d+d) mod d);
end.

评测结果
编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(3,7) Note: Local variable "c" not used
Linking foo.exe
25 lines compiled, 0.0 sec , 28032 bytes code, 1628 bytes data
1 note(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 432 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 428 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 428 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 428 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 432 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 428 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 428 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 428 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 428 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 432 KiB, score = 10
Accepted, time = 30 ms, mem = 432 KiB, score = 100
代码
program tuoou;
var
a,b,c,d,x,y:longint;
procedure tuo(a,b:longint);
var
t:longint;
begin
if (a mod b=0) then
begin
x:=0;
y:=1;
exit;
end;
tuo(b,a mod b);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;

begin
readln(a,b);
d:=b;
tuo(a,b);
x:=((X mod d)+d) mod d;
writeln(x);
end.

直接套模板AC的
#include <cstdio>
int exGcd(int a,int b,int &x,int &y)
{
if(!b) {
x=1;y=0;return a;
}
else {
int ans=exGcd(b,a%b,x,y);
int temp=x;
x=y;
y=temp-a/b*y;
return ans;
}
}

bool solve(int a,int b,int c,int &x,int &y)
{
int gcd=exGcd(a,b,x,y);
if(c%gcd) return false;
else {
int k=c/gcd;
x*=k;y*=k;
return true;
}
}

int getRev(int a,int m)
{
int x,y;
bool ok=solve(a,m,1,x,y);
if(ok) {
return x<0?x+m:x;
}
else return 0;
}

int main()
{
int a,m;
scanf("%d%d",&a,&m);
printf("%d",getRev(a,m));
return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
void exgcd(int a,int b,int &x,int &y)
{
if(!b){x=1;y=0;}
else{exgcd(b,a%b,y,x);y-=(a/b)*x;}
}
int main()
{
int x,y;
long a,b;
scanf("%d%d",&a,&b);
exgcd(a,b,x,y);
printf("%d\n",(x+b)%b);
return 0;
}

#include <cstdlib>
#include <iostream>

using namespace std;

int x,y;

int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}

int main()
{
long int a,b;
cin>>a>>b;
int r=exgcd(a,b,x,y);
if(r==1)
cout<<((x+b)%b);
return 0;
}

#include<cstdio>
using namespace std;

void exgcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1, y = 0;
return;
}
exgcd(b, a%b, x, y);
int bri = x;
x = y;
y = bri - a/b*x;
}

int main()
{
int a, b, x = 0, y = 0;
scanf("%d%d", &a, &b);
exgcd(a, b, x, y);

printf("%d", (x+b)%b);
return 0;
}
扩展欧几里得算法~~

#include<iostream>
#include<cstring>
int gcd(int a,int b,int &x,int &y)
{
if (b==0)
{
x=1,y=0;
return a;
}
int x1,y1,r;
r=gcd(b,a%b,x1,y1);
x=y1;y=x1-(a/b)*y1;
return r;
}

int main()
{
int a,b,x,y,r;
scanf("%d%d",&a,&b);
r=gcd(a,b,x,y);
printf("%d",(x+b)%b);
return 0;
}

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

long a,b,x,y;
void extEuclid(long a,long b,long *x,long *y)
{ long tmp;
if (b==0)
{
*x=1;
*y=0;
return;
}
extEuclid(b,a%b,x,y);
tmp=*x;
*x=*y;
y=tmp-(a/b)(*x);
}

int main()
{
scanf("%ld %ld",&a,&b);
extEuclid(a,b,&x,&y);
while(x<=0) x+=b;
printf("%ld\n",x);
return 0;
}

#include<iostream>
#include<cstring>

int ex_gcd(int a,int b,int &x,int &y)
{
if (b==0)
{
x=1,y=0;
return a;
}
int x1,y1,r;
r=ex_gcd(b,a%b,x1,y1);
x=y1,y=x1-(a/b)*y1;
return r;
}

int main()
{
freopen("mod.in","r",stdin);
freopen("mod.out","w",stdout);

int a,b,x,y,r;
scanf("%d%d",&a,&b);
r=ex_gcd(a,b,x,y);
printf("%d",(x+b)%b);

return 0;
}

Code

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

void exGcd(int a,int b,int &x,int &y)
{
if(b==0) { x=1, y=0; return;}
exGcd(b,a%b,x,y);
int tmp=x;
x=y, y=tmp-(a/b)*x;
}

int main()
{
int a,b,x,y;
cin>>a>>b;
exGcd(a,b,x,y);
cout<<(x+b)%b;
return 0;
}

扩展欧几里得算法，注意输出必须是正整数。

Pascal Code

procedure gcd(a,b:int64;var d,x,y:int64);
begin
if b=0 then begin d:=a;x:=1;y:=0;end
else begin gcd(b,a mod b,d,y,x);y:=y-x*(a div b);end;
end;
var
a,b,d,x,y:int64;
begin
readln(a,b);
gcd(a,b,d,x,y);
while x<0 do x:=x+b;
writeln(x);
end.

#include<cstdio>

struct Euclidnode
{
int d,x,y;
Euclidnode(int a,int b,int c)
{
d=a;
x=b;
y=c;
}
Euclidnode()
{
d=x=y=0;
}
};

Euclidnode Extended_Euclid(int a,int b)
{
if (b==0)
return Euclidnode(a,1,0);
Euclidnode tmp=Extended_Euclid(b,a%b);
return Euclidnode(0,tmp.y,tmp.x-a/b*tmp.y);
}

int main()
{
int A,B;
scanf("%d%d",&A,&B);
Euclidnode ans=Extended_Euclid(A,B);
if (ans.x<0) printf("%d",ans.x+B);
else printf("%d",ans.x);
return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int x,y,q,a,b;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);

}
void extend_Eulid(int a,int b)
{
if(b==0)
{
x=1;
y=0;
q=a;
return;
}
extend_Eulid(b,a%b);
int temp=x;
x=y;
y=temp-a/b*y;
}
int main()
{
cin>>a>>b;
extend_Eulid(a,b);
b/=gcd(a,b);
for(int i=0;;i++)
{
if(x>0)
{
cout<<x<<endl;
return 0;

}
else
{
x+=b;

}

}
return 0;
}

#include<iostream>
#include<string.h>
using namespace std;
int n;
char a[1025];

int fbi(int i,int j)
{
if(i<=j){
int mid=(i+j)/2,I=0,B=0;
if(i!=j){
fbi(i,mid);
fbi(mid+1,j);}
while(i<=j)if(a[i++]=='0')B++;else I++;
if(B>0 && I>0)cout<<'F';
else if(B>0)cout<<'B';
else cout<<'I';
}
return 0;
}
int main(void)
{
cin>>n>>a;

fbi(0,strlen(a)-1);

return 0;
}

#include<cstdio>
int x=1,y=0,t,a,b;
void gcd(int a,int b){if(b==0)return;gcd(b,a%b);t=x;x=y;y=t-(a/b)*x;}
main(){scanf("%d%d",&a,&b);gcd(a,b);while(x<=0)x+=b;printf("%d\n",x);}

这一题要注意一个细节
最后x要%b+b再%b防止出现负数

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 468 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 468 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 464 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 464 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 468 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 464 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 468 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 468 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 468 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 464 KiB, score = 10

Accepted, time = 0 ms, mem = 468 KiB, score = 100

哪位大牛告诉下欧几里得算法什么原理？

matrix67讲的拓欧

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
long long a,b;
long long k;
struct OJLD
{
int d;
int x;
int y;
}ojld;
OJLD gcd(int a,int b)
{
if(b==0) {ojld.d=a; ojld.x=1; ojld.y=0; return ojld;}
OJLD lojld;
lojld=gcd(b,a%b);
ojld.x=lojld.y;
ojld.y=lojld.x-a/b*lojld.y;
return ojld;
}
int main()
{
cin>>a>>b;
gcd(a,b);
if(ojld.x<0) cout<<ojld.x+b<<endl;
else cout<<ojld.x<<endl;
return 0;
}

#include <map>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
int a,b,x,y;
void gcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
}
else
{
gcd(b,a%b,x,y);
int t=x; x=y;
y=(t-(a/b)*x);
}
}
int main()
{
freopen("1781.in","r",stdin);
freopen("1781.out","w",stdout);
scanf("%d %d",&a,&b);
gcd(a,b,x,y);
while (x<=0) x+=b;
printf("%d",x);
return 0;
}