Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

MasterChief410's blog

By MasterChief410, history, 7 weeks ago, In English,

I noticed that many people were confused by the mathematics used in the soltuion of the editorial of this Div2.C question and decided to share with you my easy method for solving it. I use the property of distributivity of the lcm fucnction over gcd to simplify the solution. For three integers $$$ a, b, c$$$ we have

  • $$$ \gcd(lcm(a, b), lcm(a, c)) = lcm(a, \gcd(b, c))$$$
  • $$$ lcm(\gcd(a, b), \gcd(a, c)) = \gcd(a, lcm(b, c)) $$$

Proof: GCD and LCM Distribute Over Each Other

Hence for an array of integers,

  • $$$ \gcd(lcm(a_0, a_1), lcm(a_0, a_2) \dots lcm(a_0, a_n)) = lcm(a_0, gcd(a_1, a_2 \dots a_n)) $$$
  • $$$ \gcd(lcm(a_1, a_2), lcm(a_1, a_3) \dots lcm(a_1, a_n)) = lcm(a_1, gcd(a_2, a_3 \dots a_n)) $$$
  • $$$\dots$$$ $$$and$$$ $$$so$$$ $$$on$$$

Therefore, for every element of the array we can precalculate the $$$\gcd$$$ of its next elements. Then we can take the lcm of that precalculated value with the element and store it in a new array. This way all possible pairs will be covered. The answer of the problem will be the $$$\gcd$$$ of these elements. Time complexity of the $$$\gcd(m, n)$$$ function is $$$\log_2v$$$ where $$$v=\max(m, n)$$$. Hence, time complexity of the solution will be $$$O(n\cdot\log_2maxval)$$$ where $$$maxval$$$ is the maximum of the array. Here is the solution:

#include <bits/stdc++.h>
using namespace std;
 
long long lcm(long long a, long long b) { return (a*b)/__gcd(a, b); }
 
int main()
{
	long long n, ans=0;
	cin>>n;
	vector<long long> a(n), pregcd(n);
	
	for(int i=0; i<n; i++)
		cin>>a[i];
	
	pregcd[n-2]=a[n-1];	
	for(int i=n-3; i>=0; i--)
		pregcd[i]=__gcd(pregcd[i+1], a[i+1]);
	
	for(int i=0; i<n-1; i++)
		pregcd[i]=lcm(pregcd[i], a[i]);
	
	for(int i=0; i<n-1; i++)
		ans=__gcd(ans, pregcd[i]);
	cout<<ans<<endl;	  
}

This is my first time writing a blog so suggestions are welcome! Edit: Changed the data type of variables from int to long long.

 
 
 
 
  • Vote: I like it
  • +71
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Nice and simple solution, Great Work !!!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice solution

»
7 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Please change the data type int to long long int! Or, it will give you WA! Nice solution...

»
7 weeks ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Nice solution.I think you don't know gcd(0,x) = x so every time you took first element then did gcd.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great.This is very easy.Thanks a lot.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know why I overkilled C like this:79898086. I calculated suffix gcds and then had to calculate lcm(a[i],suf[i+1]) for all valid i. I calculated this lcm by finding prime factorizations of a[i] and suf[i+1] for which I am kicking myself :(.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great!I kwon how to solve it now.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can't we just find gcd of n-1 elements one by one and one(pairwise adjacently) and later find the lcm of first element and the gcd result?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

your editorial is awesome then actual everything from point to point