Bazout's Identity For three or more integers

Bézout's identity can be extended to more than two integers: if

gcd ( a1 , a2 , … , an ) = d

then there are integers x1 , x2 , … , xn such that

d = a1*x 1 + a2*x2 + ⋯ + an*xn

has the following properties:

• d is the smallest positive integer of this form
• every number of this form is a multiple of d

But... Why x_i < 0 does not affect the calculation to problem (Div. 2) — E, someone can explain me.

Tutorial: Here some xi<0, But Natasha can add for each par a sufficiently large number, multiple k, that xi became greater than zero, the balance from dividing the amount of tax on k from this will not change.

#include<bits/stdc++.h>

using namespace std;

int gcd(int a,int b)
{
    if(a<b)
        swap(a,b);
    return (b==0)?a:gcd(b,a%b);
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int g=0;
    for(int i=0;i<n;i++)
    {
        int t;
        scanf("%d",&t);
        g=gcd(g,t);
    }
    set<int> ans;
    for(long long i=0,s=0;i<k;i++,s+=g)
        ans.insert(s%k);
    printf("%d\n",ans.size());
    for(set<int>::iterator i=ans.begin();i!=ans.end();i++)
        printf("%d ",*i);
}