GCFLC - Editorial

PROBLEM LINK:

Code Battle: Holi Edition

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;
}