A、小G的sum

对于每个数，最小的约数是1，最大的约数是它本身。那么使用等差数列求合即可。

void solve() {
    n = read();
    ll ans = n + (1 + n) * n / 2;
    print(ans);
}

B、小G的GCD

对于单个 $F(x)$ ，很容易发现可以被 $k$ 整除的数量有 $\lfloor\frac{x}{k}\rfloor$ 个数。并且发现这些数都是等差数列，公差 $d=k$ 。
那么循环 $O(n)$ 遍历全部的 $x$ 即可找到全部的答案。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e6 + 7;
ll n, m;
ll p[N];
void solve() {
    n = read(), m = read();
    ll ans = 0;
    rep(i, m, n)
        ans += (m + (i / m) * m) * (i / m) / 2;
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

C、小G的约数

首先通过题目观察，很容易得到一个 $O(n)$ 的解法，那就是 $\sum\limits_{i=1}^n i*\lfloor\frac{n}{i}\rfloor$ 。
那么再看，如果暴力 $O(n)$ 的话，求解一次之后，最大的 $G(5*10^4)=10^9$ ，对着这个量级再次使用线性算法显然是会超时的。我们重新看上面的式子， $\lfloor\frac{n}{i}\rfloor$ 这不就是整除分块嘛，那就说明我们可以 $O(\sqrt n)$ 处理 $G(n)$ ，直接套用求解就出答案了。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e6 + 7;
ll n, m;
ll p[N];

// 1
// 1 2
// 1 3
// 1 2 4
// 1 5
// 1 2 3 6
// 1 7
// 1 2 4 8

ll G(ll x) { // \sum i*(n/i)   (n/i)使用整除分块sqrt n处理
    ll ans = 0;
    for (ll l = 1, r; l <= x; l = r + 1) {
        r = x / (x / l);
        ans += (l + r) * (r - l + 1) / 2 * (x / l);
    }
    return ans;
}

void solve() {
    n = read();
    ll ans = G(G(n));
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

D、小G的LY数对

先说最暴力的解题思路吧，我们使用 $hash$ 表做为一个计数器对全部的 $b_i$ 进行统计。
接下来枚举每一个 $a_i$ ，并且枚举不同的两个二进制位，将其翻转，既0变1，1变0。去看这个翻转之后的数在计数器中是否出现过，以及出现次数，当然这样做的复杂度就是 $O(45*n)$ ，前提你的 $hash$ 表复杂度是 $O(1)$ 并且常数不能过大，使用 $unordered\_map$ 常数巨大，大部分人用上面的方法都被卡了，当然我在赛后才交的，发现卡常之后还是可以很稳定的 $700ms$ 通过的。

这里说几个卡常很重要的点吧。

使用 $unordered\_map$ 代替 $map$ 实现计数器。
$STL$ 容器带来的扩容机制，实现常数巨大无比，那么我们就要使用 $.reserve()$ 成员函数直接初始预填充整个容器，避免后续的扩容操作。
变量放在 $for()$ 外面，如果塞在循环内部，它每次并不是直接进行赋值操作，而是新开内存在进行赋值操作，也会带来常数。
$OI$ 优化，快读快写一起上。
编译优化全开

因为代码较长，想查看请点击这里
后话：这些都是因为 $STL$ 自带的 $hash$ 表常数太离谱才卡死那么多人，正解做的是直接手写一个 $hash$ 表，差不多可以吧时间压缩在 $300ms$ ，非常快速，这里忍不住吐槽 $STL$ 常数太离谱了hhh。
这里也给个手写 $hash$ 的代码吧。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e6 + 10;
struct HashSet {
    struct node {
        int k, v, nex;
    } buf[N];
    int h[N], tot, mod = 1000009;
    void insert(int x) {
        int pos = x % mod;
        for (int i = h[pos]; i; i = buf[i].nex) {
            if (buf[i].k == x) { buf[i].v++; return; }
        }
        buf[++tot] = { x, 1, h[pos] };
        h[pos] = tot;
    }
    int find(int x) {
        int pos = x % mod;
        for (int i = h[pos]; i; i = buf[i].nex) {
            if (buf[i].k == x) return buf[i].v;
        }
        return 0;
    }
}mp;

int n, m, a[N];
void solve() {
    int n = read(), m = read();
    rep(i, 1, n)    a[i] = read();
    int x;
    rep(i, 1, m) {
        x = read();
        mp.insert(x);
    }
    ll ans = 0;
    rep(i, 1, n) {
        rep(j, 0, 29)
            rep(k, j + 1, 29) {
            x = (a[i] ^ (1 << j) ^ (1 << k));
            ans += mp.find(x);
        }
    }
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

E、小G的GLS图

很明显发现，如果 $n^2$ 遍历建图再去 $tarjan$ 找割点这个题目就搞定了，但是数据规模并不允许我们 $n^2$ 去建图。
那么我们再看题目有边的描述是 $\gcd(a_u,a_v)!=1$ ，那么我们就可以通过质因数去做为中介点，建立一张 $n*\log n$ 的图，记得如果某个素因子只有一个点有，不能新建一个这样的节点和 $i$ 连边，因为它没有别的出边，在跑 $tarjan$ 的时候会把这个点当作割点的因为它的孩子是独立的一个素数，根据割点判定条件他就为真了。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 3200 + 7;

vector<int>    prime;
bool vis[N];
int cnt, n, m, p[N * N];

void getprime() { // 欧拉筛法求素数表O(n)
    memset(vis, true, sizeof(vis));
    cnt = 0;
    for (int i = 2; i < N; ++i) {
        if (vis[i]) prime.push_back(i), ++cnt;
        for (int j = 0; j < cnt; ++j) {
            if (i * prime[j] >= N) break;
            vis[i * prime[j]] = false;
            if (i % prime[j] == 0) break;
        }
    }
}

const int M = 1e5 + 7;
int a[M], dfn[M << 1], low[M << 1], tot;
bool boo[M << 1];

vector<int> v[M];
vector<int> edge[M << 1];

void dfs(int u, int fa) {
    dfn[u] = low[u] = ++tot;
    int child = 0;
    for (auto& v : edge[u]) {
        if (v == fa)    continue;
        ++child;
        if (!dfn[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u] and (fa != 0 or child >= 2))
                boo[u] = 1;
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
}

void solve() {
    n = read();
    rep(i, 1, n)    a[i] = read();
    getprime();
    map<int, int> mp;
    rep(i, 1, n) {
        int x = a[i];
        for (auto& it : prime) {
            if (it > x)    break;
            if (x % it == 0) {
                ++mp[it];
                v[i].push_back(it);
                while (x % it == 0)    x /= it;
            }
        }
        if (x != 1) ++mp[x], v[i].push_back(x);
    }
    m = n;
    rep(i, 1, n) {
        for (auto& it : v[i]) {
            if (mp[it] == 1)    continue;
            if (!p[it])    p[it] = ++m;
            edge[i].push_back(p[it]);
            edge[p[it]].push_back(i);
        }
    }
    rep(i, 1, n)
        if (!dfn[i])    dfs(i, 0);
    int ans = 0;
    rep(i, 1, n)    ans += boo[i];
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

牛客练习赛77

A、小G的sum

B、小G的GCD

C、小G的约数

D、小G的LY数对

E、小G的GLS图