1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

auto sieve(auto n, auto&& pri, auto&& np) {
    np.resize(n + 1);
    for (auto i = 2; i <= n; i ++) {
        if (not np[i]) pri.push_back(i);
        for (auto j : pri) {
            if (i * j > n) break;
            np[i * j] = true;
            if (i % j == 0) break;
        }
    }
}

1
2
3
4
5
6
7

auto pow(auto a, auto b, auto p) {
    auto res = 1;
    for (; b; b /= 2, a = 1ll * a * a % p)
        if (b % 2)
            res = 1ll * res * a % p;
    return res;
}