比赛链接

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的排列

留坑。