牛客练习赛77 部分题解
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的排列
留坑。
赞 (0)