Codeforces Round #641 (Div. 2) C

Codeforces Round #641 (Div. 2) C

/ 0评 / 1336次 / 2

Description

给定\(n\)个正整数,求出\(gcd(\{lcm({ai,aj}) | i<j\})\)

Input

第一行一个整数\(n\)

第二行\(n\)个整数

Output

输出答案

Analysis

一条属实有点意思的题目。

结束以后听大佬说是分解定理做,寻思半天没琢磨透,后来还是走的暴力+优化路线。

不妨先看暴力代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100005];
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int n;
    scanf("%d", &n);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        for (int j = 0; j < i; j++)
        {
            int lcm = (a[j] * a[i]) / __gcd(a[j], a[i]);
            if (ans == 0)
            {
                ans = lcm;
            }
            else
            {
                ans = __gcd(ans, lcm);
            }
        }
    }
    printf("%d", ans);
    return 0;
}

算法的复杂度卡在两个for手上,每一次就\(a[i]\)与之前所有数的\(lcm\)时运算过多,考虑优化。可以发现的是\(a[i]\)与之前所有数的\(lcm\)再求\(gcd\)与\(a[i]\)与之前所有数求\(gcd\)再\(lcm\)没有区别

准确的说,对\(a,b,c\)可以证明

$$gcd(lcm(a,c),lcm(b,c))=lcm(gcd(a,b),c)$$

证明较为巧妙,提供如下

需要首先得到引理1

由唯一分解定理可知,任何一个数都可被分解成若干个素数的幂积

我们对一素数\(p\)讨论,有

$$lcm(p^a,p^b)=p^{max(a,b)}$$

$$gcd(p^a,p^b)=p^{min(a,b)}$$

接下来我们需要得到引理2

$$max(min(a,b),c)=min(max(a,c),max(b,c))$$

由对称性不妨假设\(a<=b\),则\(max(a,c)<=max(b,c)\)易得上结论成立

相信聪明的你已经发现了引理2实质上是对需证明结论对单一素数情况下的特殊情况

我们对一素数\(p\)讨论

原式则有

$$gcd(lcm(p^a,p^c),lcm(p^b,p^c))$$

$$=min(max(p^a,p^c),max(p^b,p^c))$$

$$=max(min(p^a,p^b),c)$$

$$=lcm(gcd(p^a,p^b),p^c)$$

$$Q.E.D$$

于是,我们就可以对求lcm的过程做前缀gcd的优化

即可得解。

Accepted Code

/*
 * @Author: Gehrychiang
 * @LastEditTime: 2020-05-13 01:29:58
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 * @ProbTitle: (记得补充题目标题)
 */
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
ll gcdd[100005];
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int n;
    scanf("%d", &n);
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        if (i == 0)
        {
            gcdd[0] = a[0];
        }
        else
        {
            gcdd[i] = __gcd(gcdd[i - 1], a[i]);
            ll lcm = (a[i] / __gcd(a[i], gcdd[i - 1]) * gcdd[i - 1]);
            if (ans == 0)
            {
                ans = lcm;
            }
            else
            {
                ans = __gcd(ans, lcm);
            }
        }
    }
    printf("%lld", ans);
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.65347