CF1349A

· · 题解

顶楼大佬的思路真是妙，我就只说一些理解和补充吧。

如果理解大佬的思路的话，你就会明白：

题意是要求：

\gcd\lbrace\operatorname{lcm}(a_i,a_j)|i<j\rbrace

那么拆开来看，对于每一个质数 p，设 e_i 是最大的使得 p^{e_i}|a_i 的数，那么我们相当于求：

\min \lbrace \max(e_i,e_j)|i<j\rbrace

容易看出这是求e_i的次小值。

一种思路是直接暴力分解因式，这样是 O(\sum\sqrt a_i) 的由于题目超大的时间限制可以通过本题。

但大佬将这个式子做了一个变形：

\gcd\lbrace\operatorname{lcm}(a_i,a_j)|i<j\rbrace=\frac{\gcd\lbrace a_ia_j|i<j\rbrace}{\gcd\lbrace\gcd(a_i,a_j)|i<j\rbrace}

一开始，我大惑不解：\gcd 运算明明不能将除法分离出来啊？

但后来，我明白了：对于每个质数 p，\gcd\lbrace a_ia_j|i<j\rbrace 相当于求出了其指数的最小值和次小值之和，\gcd\lbrace\gcd(a_i,a_j)|i<j\rbrace 则相当于求出了其指数的最小值，两者相减便是答案。

而这两个式子可比 \operatorname{lcm} 好维护多了！

我们继续推式子：

\gcd\lbrace\operatorname{lcm}(a_i,a_j)|i<j\rbrace=\frac{\gcd\lbrace a_ia_j|i<j\rbrace}{\gcd\lbrace\gcd(a_i,a_j)|i<j\rbrace} =\frac{\gcd\lbrace a_i\gcd\lbrace a_j|j<i\rbrace\rbrace}{\gcd\lbrace a_i\rbrace}

(似乎题解区的大佬考虑了重复的情况呢，虽然这里并不会影响正确性，在这里本蒟蒻提出一个小小的批评）

依照上面的方法，每到一个 a_i，我们只需要乘上我们同时间处理的 \gcd ，然后对答案求 \gcd 即可。可以给出我们的程序了！时间复杂度 O(n+\log a_i)，空间复杂度 \Theta(n)。

//尊前不用翠眉颦，人生如逆旅，我亦是行人
#include<fstream>
using namespace std;
const int MAXN=1e5+1;
int n,a[MAXN],g;
long long dc=1;
long long gcd(long long a,long long b)
{
    return (a%b==0)?b:gcd(b,a%b);
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    g=a[0];
    dc=1ll*a[0]*a[1];
    for(int i=1;i<n-1;i++)
    {
        long long part=1ll*g*a[i];
        g=gcd(a[i],g);
        dc=gcd(dc,part);
    }
    dc=gcd(dc,1ll*g*a[n-1]);
    g=gcd(a[n-1],g);
    printf("%lld",dc/g);
    return 0;
}

同样给出不需要数组的程序。时间复杂度 O(n+\log a_i)，证明看这篇，空间复杂度理论上 O(1) 实际上 \gcd 有影响。

//尊前不用翠眉颦，人生如逆旅，我亦是行人
#include<fstream>
using namespace std;
int n,a,g;
long long dc;
long long gcd(long long a,long long b)
{
    return !b?a:gcd(b,a%b);
}
int main()
{
    scanf("%d",&n);
    g=dc=0;
    for(int i=0;i<n;++i)
    {
        scanf("%d",&a);
        dc=gcd(1ll*g*a,dc);
        g=gcd(a,g);
    }
    printf("%lld",dc/g);
    return 0;
}

感谢各位大佬提供的思路。

最后给出一个有趣又简单的说明 \gcd 复杂度较紧上界的方法辅助复杂度理解。