Codeforces Round #641 Div1.A Orac and LCM 中文题解

· · 题解

Orac and LCM 中文题解

下文中p代表质数；v为常数，代表a_i的最大值；ans代表答案。

Observation. p^k\ \mid\ ans ， 当且仅当：对于 i=1,2,3,...,n，有至少 n-1 个 i 满足 p^k\ \mid\ a_i。

Proof. 若至多 n-2 个 i 满足 p^k \mid a_i，则存在 x\neq y，满足 p^k\nmid a_x 且 p^k\nmid a_y。所以p^k \nmid \textrm{lcm}(\{a_x,a_y\})，于是 p^k\ \nmid\ ans；反之，若至少 n-1 个 p^k \mid a_i ，则任意两个数中必然至少有一个是p^k的倍数。那么对于任意x,y，必然有p^k \mid \textrm{lcm}(\{a_x,a_y\})，于是 p^k\ \mid\ ans。

接下来有两种做法：

Solution 1. 设 d_i 为删去 a_i ，剩下 n-1 个数所构成的集合。那么，\gcd(d_i) 必然被至少 n-1 个数整除，且若有至少 n-1 个 i 满足 p^k\ \mid\ a_i，必然对于某个 i 满足p^k \mid \gcd(d_i)。那么由Observation，ans=\textrm{lcm}(\{\gcd(d_1),\gcd(d_2),\gcd(d_3),...,\gcd(d_n)\})。

考虑如何快速计算\gcd(d_i)。对于每个i，维护前缀pre_i=\gcd(\{a_1,a_2,...,a_i\})与后缀suf_i=\gcd(\{a_{i},a_{i+1},...,a_n\})。那么\gcd(d_i)=\gcd(\{pre_{i-1},suf_{i+1}\})，而pre和suf显然都是可以O(n\cdot \log(v))计算的。

时间复杂度：O(n \log v)

Solution 2. 枚举值域内的每个质数。对于质数 p，我们枚举每个 a_i，计算出最大的 k_i，满足 p^{k_i} \mid a_i。分析Observation可知，所有 i 中次小的 k_i 就是ans的分解质因数形式中p的幂次。一个优化是，枚举时如果发现已经有 2 个 a_i 无法被 p 整除了，那么 ans 也必然无法被 p 整除，于是我们就可以不再枚举剩余的 a_i 了。

时间复杂度：对于每个质数，最多出现两次枚举到的 a_i 不能被 p 整除的情况。对于每个数，最多被除 \log v 次。所以，时间复杂度就是 O(v+n\log v)。

Problem and Tutorial by mydiplomacy

Code for Solution 2:

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;

const int maxn=100005;

int n;
ll a[maxn];

ll pre[maxn],suf[maxn];

ll gcd(ll x, ll y)
{
    if(y==0) return x;
    else return gcd(y,x%y);
}

ll ga,ans;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    pre[1]=a[1]; suf[n]=a[n];
    for(int i=2;i<=n;i++)
        pre[i]=gcd(pre[i-1],a[i]);
    for(int i=n-1;i>=1;i--)
        suf[i]=gcd(suf[i+1],a[i]);
    for(int i=0;i<=n-1;i++)
    {
        if(i==0)
            ans=suf[2];
        else if(i==n-1)
            ans=ans*pre[n-1]/gcd(pre[n-1],ans);
        else
            ans=ans*gcd(pre[i],suf[i+2])/gcd(gcd(pre[i],suf[i+2]),ans);
    }
    printf("%lld\n",ans);
    return 0;
}