We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Mathematics
- Number Theory
- Salary Blues
- Discussions
Salary Blues
Salary Blues
Sort by
recency
|
27 Discussions
|
Please Login in order to post a comment
// C++ 20........solution
const int N = 100000; long long arr[N];
long long gcd(long long a, long long b) { if(a < 0){ a = -a; }
}
int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */
}
SPOILER SOLUTION
Does anyone know what is the exact amount of salary tal dilian gives to their employes?
If you're ready to do some precomputation, then you can reduce it to a constant time update. There are two important (though very basic) identities that we need to know before we discuss the solution. They are:
gcd(a,b)=gcd(a,b−a)
gcd(a,b,c)=gcd(a,gcd(b,c)) =gcd(gcd(a,b),c)
Based on these two, the following identity follows immediately: gcd(a1,a2,a3...an)= gcd(a1,gcd(a2−a1,a3−a2...an−an−1))
Now note that when you increment all numbers by a constant, their differences don't change at all and so the quantity gcd(a2−a1,a3−a2...an−an−1) doesnt' change either. And so we can see that the gcd of all the numbers changes just because a1 changes.