Codeforces Round #641 Div1.A Orac and LCM 中文题解
Caro23333
2020-04-30 11:15:12
### 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:
```cpp
#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;
}
```