soj1092扩展欧几里德算法.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 32 行

#include<stdio.h>

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

int main(void)
{
    long a,m;
    while(scanf("%ld%ld",&a,&m)&&(a||m))
    {
        long x,y;
        egcd(m,a,y,x);
        x=((x%m)+m)%m;
        printf("%ld\n",x);
    }
    return 0;
}