本文共 5667 字，大约阅读时间需要 18 分钟。

A  小G的sum

的最小的约数是，的最大的约数是。

#include<bits/stdc++.h>using namespace std ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int n ;    cin >> n ;    long long ans1 = n ;    long long ans2 = 1ll * n * (n + 1) / 2 ;    cout << ans1 + ans2 << '\n' ;    return 0 ;}

 
B  小G的GCD

#include<bits/stdc++.h>using namespace std ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int n , k ;    long long ans = 0 ;    cin >> n >> k ;    auto cal = [&](int x)    {        return 1ll * k * x * (x + 1) / 2 ;    } ;    for(int i = 1 ; i <= n ; i ++)  ans += cal(i / k) ;    cout << ans << '\n' ;    return 0 ;}

C  小G的约数

，整除分块即可。

#include<bits/stdc++.h>using namespace std ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int n ;    cin >> n ;    auto cal = [&](long long l , long long r)    {        long long a1 = l ;        long long n = r - l + 1 ;        long long d = 1 ;        return n * a1 + n * (n - 1) * d / 2 ;    } ;    auto G = [&](long long n)    {        long long ans = 0 ;        for(long long l = 1 , r ; l <= n ; l = r + 1)        {         r = n / (n / l) ;         ans += 1ll * cal(l , r) * (n / l) ;        }        return ans ;    } ;    cout << G(G(n)) << '\n' ;    return 0 ;}

D  小G的LY数对

开局有人分钟过了，以为直接暴力做就行，成瓜皮。

仔细分析等价于

具体写的时候要容斥，因为会算重复。

时间复杂度降低为。

#include<bits/stdc++.h>using namespace std ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int n , m ;    cin >> n >> m ;    vector<int> a(n) ;    vector<int> b(m) ;    for(int i = 0 ; i < n ; i ++)  cin >> a[i] ;    for(int i = 0 ; i < m ; i ++)  cin >> b[i] ;    vector<int> c , d ;    for(int i = 0 ; i < n ; i ++)        for(int j = 0 ; j < 30 ; j ++)            c.push_back((a[i] ^ (1 << j))) ;    for(int i = 0 ; i < m ; i ++)        for(int j = 0 ; j < 30 ; j ++)            d.push_back((b[i] ^ (1 << j))) ;    long long ans = 0 ;    sort(c.begin() , c.end()) ;    sort(d.begin() , d.end()) ;    int cur = 0 ;    int siz1 = c.size() , siz2 = d.size() ;    for(int i = 0 ; i < siz1 ; i ++)    {        int j = i ;        while(j + 1 < siz1 && c[j + 1] == c[j])  j ++ ;        while(cur + 1 < siz2 && d[cur] < c[i])  cur ++ ;        int p = cur ;        if(c[i] == d[cur])        {            while(p + 1 < siz2 && d[p + 1] == d[p])  p ++ ;            ans += 1ll * (j - i + 1) * (p - cur + 1) ;            //cout << c[i] << ' ' << j - i + 1 << ' ' << p - cur + 1 << '\n' ;            cur = p ;        }            i = j ;    }    //cout << ans << '\n' ;    sort(a.begin() , a.end()) ;    sort(b.begin() , b.end()) ;    cur = 0 ;    siz1 = a.size() , siz2 = b.size() ;    for(int i = 0 ; i < siz1 ; i ++)    {        int j = i ;        while(j + 1 < siz1 && a[j + 1] == a[j])  j ++ ;        while(cur + 1 < siz2 && b[cur] < a[i])  cur ++ ;        int p = cur ;        if(a[i] == b[cur])        {            while(p + 1 < siz2 && b[p + 1] == b[p])  p ++ ;            ans -= 1ll * (j - i + 1) * (p - cur + 1) * 30 ;            cur = p ;        }            i = j ;    }    cout << ans / 2 << '\n' ;    return 0 ;}

E  小G的GLS图

首先分析是否存在某种数学关系，从而避免建图找割点。但是手画一些，会发现不建图无法找到割点。

然后就开始思考如何简化建边，不能直接暴力建边。然后思考质因子分解，每个质因子在个数存在，直接建边是的，但是发现我其实只要建出一个长度是的环就好了，没必要建出稠密图。

因此建出图跑一遍求割点就好了。

时间复杂度的瓶颈是质因子分解。

#include<bits/stdc++.h>using namespace std ;const int maxn = 1e7 + 10 ;int cnt = 0 ;bool vis[maxn] ;int prime[maxn] ;int id[maxn] ;void get_prime(int up) //素数筛{    memset(vis , 0 , sizeof(vis)) ;    vis[1] = 1 ;    for(int i = 2 ; i <= up ; i ++)    {        if(!vis[i])         prime[++ cnt] = i , id[i] = cnt ;        for(int j = 1 ; j <= cnt && i * prime[j] <= up ; j ++)        {            vis[i * prime[j]] = 1 ;            if(i % prime[j] == 0) break ;        }    }}vector<int> v[700000 + 10] ;void init(int x , int c){    int now = 1 ;    for(int i = 1 ; prime[i] * prime[i] <= x ; i ++)    {        if(x % prime[i] == 0)          {            while(x % prime[i] == 0)  x /= prime[i] ;            now *= prime[i] ;            v[i].push_back(c) ;        }    }    if(x > 1)  v[id[x]].push_back(c) ;}int head[maxn] ;int num = 1 ;int dfn[maxn] , low[maxn] , parent[maxn];int ans = 0 ;int cut[maxn] ;struct Node{    int v , next ;} edge[maxn] ;void add(int u , int v){    edge[num].v = v ;    edge[num].next = head[u] ;    head[u] = num ++ ;}void add1(int u , int v){    add(u , v) ;    add(v , u) ;}void dfs(int u){    static int count = 0 ;    int children = 0 ;    int v ;    dfn[u] = low[u] = ++ count ;    for(int i = head[u] ; i != 0 ; i = edge[i].next)    {        v = edge[i].v ;        if (dfn[v] == 0)        {            children ++ ;            parent[v] = u ;            dfs(v) ;            low[u] = min(low[u] , low[v]) ;            if(cut[u] == 0 && (parent[u] == -1 && children >= 2 || parent[u] != -1 && low[v] >= dfn[u]))            {                ans ++ ;                cut[u] = 1 ;                //cout << u << '\n' ;                      }                    }        else if (v != parent[u])        low[u] = min(low[u], dfn[v]) ;    }}int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    get_prime(10000000) ;    int n ;    cin >> n ;    for(int i = 0 ; i < n ; i ++)    {        int x ;        cin >> x ;        init(x , i + 1) ;    }    memset(head , 0 , sizeof(head)) ;    memset(parent , -1 , sizeof(parent)) ;    memset(dfn , 0 , sizeof(dfn)) ;    for(int i = 1 ; i <= cnt ; i ++)    {        int siz = v[i].size() ;        if(siz >= 2)        {            for(int j = 0 ; j < siz - 1 ; j ++)                add1(v[i][j] , v[i][j + 1]) ;            add1(v[i][0] , v[i][siz - 1]) ;        }    }    for(int i = 1 ; i <= n ; i ++)        if(dfn[i] == 0)  dfs(i) ;    cout << ans << '\n' ;    return 0 ;}

F  小G的排列

留坑。