PROBLEM LINK:
Author: Om
Tester: Tejus Kaw
Editorialist: Om
DIFFICULTY:
Easy
PREREQUISITES:
GCD , LCM
PROBLEM:
find the HCF of LCMs of all pairs of elements in the given sequence
EXPLANATION:
In this tutorial p stands for a prime, v stands for the maximum of ai and ans stands for the answer.
Observation.
- p^k ∣ ans if and only if there are at least n−1 integers in a that s.t. pk∣ a_i
Proof.
if there are at most n−2 integers in a that s.t. pk∣ a_i, there exists x≠y s.t. pk∤a_x and pk∤a_y, so pk∤lcm({a_x,a_y}) and pk ∤ ans. On the contrary, if there are at least n−1 integers in a s.t. pk∣ a_i, between every two different a_i there will be at least one multiple of pk. So for every (x,y), pk∣lcm({a_x,a_y}). Therefore pk ∣ ans .
Solution 1.
Define d_i as a set that consists of all the numbers in a except a_i. So gcd(d_i) is divisible by at least n−1 numbers in a. Also, if at least n−1 integers in a pk ∣ ai, we can always find i s.t. pk∣gcd(d_i).
According to the Observation,
ans=lcm({gcd(d_1),gcd(d_2),gcd(d_3),...,gcd(d_n)}) .
Now consider how to calculate gcd(d_i). For every i, calculate pre_i=gcd({a_1,a_2,...,a_i}) and sufi=gcd({a_i,a_i+1,...,a_n}). Therefore gcd(d_i)=gcd({pre_i−1,suf_i+1}) and we can get pre and suf in O(n⋅log(v)) time.
Time complexity: O(nlogv)
Solution 2.
Enumerate every prime ≤v. For a prime p, enumerate every ai and calculate ki which stands for the maximum integer that s.t. pk_i∣a_i. According to the Observation, the second smallest k_i is the maximum integer k that s.t. pk∣ans. Now let’s optimize this solution. If there has been at least two a_i not divisible by p, then p∤ans, so just stop enumerate a_i .
Time complexity of the optimized solution is O(v+nlogv) because every integer can be divided for at most logv times.
SOLUTIONS:
Setter's Solution
#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;
}