### On the most recent Bleddest Div 2, I used gcd instead of mod, thinking I wouldn't get punished.↵
↵
Becuase O(n^2 log 10^9) = 30 * 5000 * 5000 = 7.5 * 10^8 which should pass.↵
↵
But it turns out that the C++ built in gcd uses the Euclidian Algorithm: ↵
↵
```↵
int gcd (int a, int b) {↵
return b ? gcd (b, a % b) : a;↵
}↵
```↵
↵
Hacked Submission: https://codeforces.me/contest/2283/submission/397357386↵
↵
#### So the next time you want to compute GCD, use Stein’s algorithm:↵
↵
```↵
int gcd(int a, int b) {↵
if (!a || !b)↵
return a | b;↵
unsigned shift = __builtin_ctz(a | b);↵
a >>= __builtin_ctz(a);↵
do {↵
b >>= __builtin_ctz(b);↵
if (a > b)↵
swap(a, b);↵
b -= a;↵
} while (b);↵
return a << shift;↵
}↵
```↵
↵
I get the easy AC after getting hacked :( ↵
https://codeforces.me/contest/2283/submission/397490186↵
↵
So what do you guys think about the built in gcd?↵
↵
Becuase O(n^2 log 10^9) = 30 * 5000 * 5000 = 7.5 * 10^8 which should pass.↵
↵
But it turns out that the C++ built in gcd uses the Euclidian Algorithm: ↵
↵
```↵
int gcd (int a, int b) {↵
return b ? gcd (b, a % b) : a;↵
}↵
```↵
↵
Hacked Submission: https://codeforces.me/contest/2283/submission/397357386↵
↵
#### So the next time you want to compute GCD, use Stein’s algorithm:↵
↵
```↵
int gcd(int a, int b) {↵
if (!a || !b)↵
return a | b;↵
unsigned shift = __builtin_ctz(a | b);↵
a >>= __builtin_ctz(a);↵
do {↵
b >>= __builtin_ctz(b);↵
if (a > b)↵
swap(a, b);↵
b -= a;↵
} while (b);↵
return a << shift;↵
}↵
```↵
↵
I get the easy AC after getting hacked :( ↵
https://codeforces.me/contest/2283/submission/397490186↵
↵
So what do you guys think about the built in gcd?↵
