P1082 同余方程

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;
}