Cod sursa(job #2780663)

Utilizator VladMxPMihaila Vlad VladMxP Data 7 octombrie 2021 16:27:31
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("f.in");
int m,n;

void euclid(int a,int b,int d,int &x, int &y) // a*x+b*y=d
{
    if(b==0)
    {
        x=1;
        y=0;
    }
    else
    {
        int x0,y0;
        euclid(b,a%b,d,x0,y0);
        x=y0;
        y=x0-(a/b)*y0;
    }
}

int main()
{
    int a,b,c,r;
    fin>>m>>n;
    // cmmdc(m,n,m+n)
    //if(n>m)swap(m,n);
    a=m;b=n;r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    a=m+n;r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    c=b;
    cout<<c<<" ";
    a=b=0;
    euclid(m,-n,c,a,b); // a*m-b*n=c;
    cout<<a<<" "<<b;
}