Bitwise operation

Play with bit O_O
Assuming 32-bits integers

1
2
3
4
5
6
def Abs(n):
    return (n ^ (n >> 31)) - (n >> 31)
def max(a, b):
    return b & ((a - b) >> 31) | a & (~(a - b) >> 31)
def min(a, b):
    return a & ((a - b) >> 31) | b & (~(a - b) >> 31)

Rem and Mod

know it too late qwq

Divisions

Floored : quotient floored toward negative infinity, remainder same sign as the divisor
Truncated : quotient truncated toward zero, remainder as the same sign as the dividend
Euclidean : quotient truncated to keep the remainder positive

Examples

% : In python, the symbol % is actually a modulo, not a remainder.
a = -5, b = 3
c = a / b = -1.67…

Rem

Round off the fractional part of c in the direction of 0, after which c = -1

Rem = a - b * c = -5 - (3 * (-1)) = -2

Mod

Round c to negative infinity, after which c = -2

Mod = a - b * c = -5 - 3 * (-2) = 1

Interval gcd

Wl,r=(r−l+1)×gcd(Al,Al+1,⋯ ,Ar)。W_{l, r} = (r − l + 1) \times gcd(A_l, A_{l+1}, \cdots, A_r )。

Find max⁡Wl,r\max {W_{l, r}}

Solution:

There are at most log⁡N\log N distinct gcd’s inside n numbers.

So enumerate i, find all the different gcd’s before i, and then gcd them separately with aia_{i}
Note down each different gcd and the beginning of their position.
Then traverse the gcd once to find the largest weight.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
struct node {
    ll data;
    ll w;
};
ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}
int n, m = 0;
const int maxn = 100010;
ll a[maxn], ans = -1;
node res[maxn];
map<ll, ll> Map;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++) {
        int k = 0;
        Map.clear();
        for (int j = 0; j < m; j++) {
            ll t = gcd(a[i], res[j].data);
            if (Map[t] == 0) {
                Map[t]++;
                res[k].data = t;
                res[k].w = res[j].w;
                k++;
            }
        }
        if (Map[a[i]] == 0) {
            Map[a[i]]++;
            res[k].data = a[i];
            res[k].w = i;
            k++;
        }
        m = k;
        for (int j = 0; j < m; j++)
            if (res[j].data * (i - res[j].w + 1) > ans)
                ans = res[j].data * (ll) (i - res[j].w + 1);
    }
    cout << ans << "\n";
    return 0;
}