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);
}
Here it goes: Firstly let me explain what's the need for xi < 0. It is used to emphasize the point that any multiple of gcd modulo k can be obtained using the given coins.
What do I mean by that? Well let's suppose that k = 10 and you had only 2 coins 4 and 6, their gcd is 2. But since 2 = 1 * 6 + (-1) * 4, one might suspect that 2 might never be obtined from a linear combination of the given coins, but 2 modulo 10 can be obtained by taking 2 coins of value 6 and none of 4 or 3 coins of 4 and none of 6.
This argument is a specific version of the more general one, which says that any multiple of gcd modulo m can be obtained by taking an appropriate no. of coins.
To prove this, consider a positive value that can be obtained from the coins. We know by Bezout's identity that it will be a multiple of gcd. But suppose that in this linear combination, some xi < 0, which shows that we took xi < 0 total coins of value ai, which is not quite possible. But, now if we add k more coins of value xi, the value of the amount modulo k will not change, since we are doing all calculations modulo k. If the new value of xi, is still negative we can keep on adding coins of value ai in groups of k, until the value of xi becomes positive. Now, in doing this, we have not changed the value of amount modulo k, but now since xi is positive (or maybe 0), we have ensured that we can give xi number of coins for the coin of value ai, and still obtain the same value modulo k. Doing this with all the coefficients, will ensure that by using 0 or more coins of every value, we can pay this amount modulo k.
With this, we have proved that any positive multiple of gcd can be obtained as the value, but since we are doing the computation modulo k, we know that there are only a small number of possibilities for the amount modulo k and once we obtain a value which we had already obtained earlier, we know that the values will go on cycling around repeating themselves, so we can stop at that point.
Hope this explanation makes it clear.
Hello, I thank you!. After several hours I came to the same conclusion yesterday.