P1082 同余方程
Captain_Paul
2018-09-02 20:30:07
NOIP2012的同余方程模板题
```
//对于不完全为0的非负整数a,b,一定存在整数对(x,y),使得gcd(a,b)=ax+by;
#include<iostream>
#include<cstdio>
using namespace std;
int a,b;
void work(int a,int b,int &d,int &x,int &y)
{
if (!b)
{
x=1; y=0; d=a;
return;
}
work(b,a%b,d,y,x);
y=y-a/b*x;
}
int main()
{
scanf("%d%d",&a,&b);
int x,y,d;
work(a,b,d,x,y);
printf("%d",(x+b)%b);
return 0;
}
```