首页 > 其他分享 >Codeforces Round 973题解(E)

Codeforces Round 973题解(E)

时间:2024-09-27 20:49:25浏览次数:7  
标签:... 973 gcd int 题解 元素 Codeforces 选择 使得

E. Prefix GCD

假设我们从一个空集合\(b\)开始,不断从\(a\)数组中选择一个元素添加到\(b\)集合的尾部,当把\(a\)数组的元素全部添加到\(b\)中后,得到的\(b\)即为所求的rearrange后的\(a\)。

结论1:

每次选择使得其和当前\(b\)中所有元素的最大公约数最小的那个\(a_i\)加入到\(b\)的末尾,即选择\(a_i\),使得\(gcd(b_1, b_2, ..., b_k, a_i)\)最小(假设当前\(b\)的大小为\(k\)),这样得到的\(b\)是最优的。

证明1:

假设当前的\(b\)集合为:
\(b_1, b_2, ..., b_k\),此\(b\)集合即为正确答案的\(b\)的前\(k\)个元素。
使得\(gcd(b_1, b_2, ..., b_k, a_i)\)取得最小值的a_i是\(A\)。
而正确方案中这个步骤应该选择的\(a_i\)是\(B\)。那么有\(gcd(b_1, b_2, ..., b_k, A) <= gcd(b_1, b_2, ..., b_k, B)\)。

结论2:

可以把正确方案的\(b = \{b_1, b_2, ..., b_k, B\}\)①
替换成:
\(b = \{b_1, b_2, ..., b_k, A, B\}\),这样结果不会变坏。②

证明2:

设\(f = \gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n)\),
则①的\(f\)为\(gcd(b_1) + gcd(b_1, b_2) + ... + gcd(b_1, b_2, ..., b_k) + gcd(b_1, b_2, ..., b_k, B)\)
②的\(f\)为\(gcd(b_1) + gcd(b_1, b_2) + ..., + gcd(b_1, b_2, ..., b_k) + gcd(b_1, b_2, ..., b_k, A) + gcd(b_1, b_2, ..., A, B)\)

二者不同的部分满足\(gcd(b_1, b_2, ..., b_k, B) >= gcd(b_1, b_2, ..., b_k, A) + gcd(b_1, b_2, ..., b_k, A, B)\),
因为\(gcd(b_1, b_2, ..., b_k, A) + gcd(b_1, b_2, ..., b_k, A, B) = gcd(b_1, b_2, ..., b_k, A) + gcd(b_1, b_2, ..., b_k, b_1, b_2, ..., b_k, A, B) = gcd(b_1, b_2, ..., b_k, A) + gcd(gcd(b_1, b_2, ..., b_k, A), gcd(b_1, b_2, ..., b_k, B)) <= gcd(b_1, b_2, ..., b_k, B)\)。

这用到了两个点:

  1. \(gcd(X, Y) <= |X - Y|\)
  2. \(gcd(b_1, b_2, ..., b_k, A) <= gcd(b_1, b_2, ..., b_k, B)\)

因此每次选择使得其和当前\(b\)中所有元素的最大公约数最小的那个\(a_i\)加入到\(b\)的末尾满足题意。

优化

设\(g = gcd(a_1, a_2, ..., a_n)\)
我们可以在开始计算前,将每个\(a_i\)除以\(g\),因为这样处理后,\(gcd(a_1, a_2, ..., a_n) = 1\),这意味着,我们选择一部分\(a_i\)到\(b\)中后,就可以使得\(gcd(b_1, b_2, ..., b_k)\)变为\(1\),
事实上,我们每次选择一个\(a_i\)都会使得\(gcd(b)\)下降,因为如果我们某次选择的\(a_i\)没有使得\(gcd(b)\)下降,则说明\(gcd(b)\)已经下降到了\(1\),可以退出迭代了。
最后我们再把结果乘上\(g\)。

如果不进行这一步操作,则很有可能\(gcd(b)\)永远都到不了1。这样的话我们代码中判断到\(1\)的部分应该改为\(g\)。

时间复杂度

因为每个数最多有\(log_2{x}\)个可能相同的质因数,因此只需要\(log_2{10^5}\)次添加就可以使得\(gcd(b) = 1\)。

int n;
int a[N];

void solve() {
    cin >> n;
    int gcd_all = 0;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        gcd_all = gcd(gcd_all, a[i]);
    }
    for (int i = 1; i <= n; i ++) {
        a[i] /= gcd_all;
    }
    int cur = 0, cnt = 0;
    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        int min_v = INF;
        for (int j = 1; j <= n; j ++) {
            min_v = min(min_v, gcd(cur, a[j]));
        }
        cur = min_v;
        cnt ++;
        ans += cur;
        if (cur == 1) {
            ans += n - cnt;
            break;
        }
    }
    ans *= gcd_all;
    cout << ans << '\n';
}

标签:...,973,gcd,int,题解,元素,Codeforces,选择,使得
From: https://www.cnblogs.com/lightmon5210/p/18435645

相关文章

  • ZZJC新生训练赛第一场题解
    先给出比赛链接:https://ac.nowcoder.com/acm/contest/91452下面说一下难度分层:(同一难度下按字典序排序)Easy(简单):B,FMedium(中等):A,E,HHard(困难):C,GAnti-AK(防AK):D,Icin.tie(nullptr)->sync_with_stdio(false);//加速输入输出的A游游的整数翻转将所......
  • 【洛谷】P4819 [中山市选] 杀人游戏 的题解
    【洛谷】P4819[中山市选]杀人游戏的题解题目传送门题解Tarjan我可爱的Tarjan嘻嘻qaq枚举每一个点,然后枚举每条出边,如果相连的两个点在同一个强连通分量中,或者xx......
  • 【洛谷】AT_abc178_d [ABC178D] Redistribution 的题解
    【洛谷】AT_abc178_d[ABC178D]Redistribution的题解洛谷传送门AT传送门题解一个水水的动态规划,阿巴巴巴。题目大概是这样:给定一个正整数SSS,问有多少个数满足以......
  • 【2024秋#113】锦城ACM周测题解
    2024秋#112】锦城ACM周测题解A.awa1思路这里是对答案进行二分,我们预测一个答案的范围,取这个范围的中点,试探是否可行。如果可行,将这个范围的右边的范围缩小到mid(注意我们所求是最短时间,所以当mid可行的时候我们是将预测的最大的值变小),如果不可行,说明我们预测的这个范围左边......
  • Pbootcms源码上传安装后前端显示错乱乱码问题解决方案
    PbootCMS前端显示错乱或乱码问题可能是由多种原因造成的,下面是一些可能的解决方案:检查字符集设置:确认前端页面的字符集设置是否正确。通常在HTML头部会有一个<meta>标签定义字符集,例如<metacharset="UTF-8">。同时检查PbootCMS后台的字符集设置是否与前端一致,确保数据库和......
  • 【题解】【归并排序】—— [NOIP2011 普及组] 瑞士轮
    【题解】【归并排序】——[NOIP2011普及组]瑞士轮[NOIP2011普及组]瑞士轮题目背景题目描述输入格式输出格式输入输出样例输入#1输出#1提示1.思路解析2.AC代码[NOIP2011普及组]瑞士轮通往洛谷的传送门题目背景在双人对决的竞技性比赛,如乒乓球、羽毛球、......
  • P10603 BZOJ4372 烁烁的游戏 题解
    题目传送门前置知识动态树分治|动态开点线段树|标记永久化解法考虑动态点分治。两种操作本质上是将luoguP6329【模板】点分树|震波的操作互换了下,将原需支持单点修改、区间查询的数据结构换成需支持区间修改、单点查询的数据结构即可。区间修改、单点查询的动态开......
  • Light Bulbs (Hard Version) 题解
    提供一个非常另类的解法,没有异或哈希,没有建图,没有缩点和强连通分量,而是使用了并查集和线段树的算法。由于每个颜色恰好有两种,我们考虑把两个颜色的位置\(i,j\)变成一段区间\([i,j]\)(\(i<j\)),然后每个颜色就能用一段区间\([l,r]\)表示。根据题意,如果我们激活了一个区间\([l,......
  • 【MX-J3-T3+】Tuple+ 题解
    一个比较自然的思路就是对于每个三元组\((u_i,v_i,w_i)\),把\((v_i,w_i)\)这个二元组放在属于\(u_i\)的vector里面。然后对于每一个\(i\in[1,n-3]\),把\(i\)的vector里面的所有二元组\((x,y)\)当作一条连接\(x,y\)的无向边,则我们的目的是在图中找出所有的三元环\(......
  • [ARC115E] LEQ and NEQ 题解
    我这场打的VP,结果E思考的时间比A还少。。但是我觉得我能想出这道题还是很有意义的,写篇题解记录一下。首先应该都不难想到动态规划吧?我们先使用暴力DP:设\(dp_{i,j}\)表示处理完前\(i\)个数,第\(i\)个数为\(j\)的方案数。我们考虑进行分类讨论:\(a_i≥a_{i-1}\):此时......