General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
86427880 Practice:
JKLover
1285F - 50 GNU C++17 Accepted 124 ms 15668 KB 2020-07-10 15:45:48 2020-07-10 15:45:48
 
 
→ Source
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 1e5 + 10;
int n, m = 0, mu[N], a[N], vis[N], t[N], stk[N], tp = 0, f[N];
ll ans = 0;
vector<int> fac[N];
int query(int x)
{
	int s = 0;
	for (int d : fac[x])
		s += f[d] * mu[d];
	return s;
}
void upd(int x, int c)
{
	for (int d : fac[x])
		f[d] += c;
}
int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
		m = max(m, a[i] = read());
	mu[1] = 1;
	for (int i = 1; i <= m; ++i)
	{
		fac[i].push_back(i);
		for (int j = i + i; j <= m; j += i)
			fac[j].push_back(i), mu[j] -= mu[i];
	}
	for (int i = 1; i <= n; ++i)
		if (!vis[a[i]])
		{
			for (int j : fac[a[i]])
				t[j] = 1;
			vis[a[i]] = 1;
		}
		else
			ans = max(ans, 1LL * a[i]);
	for (int x = m; x >= 1; --x)
		if (t[x])
		{
			while (tp && query(x) > 0)
			{
				if (__gcd(x, stk[tp]) == 1)
					ans = max(ans, 1LL * x * stk[tp]);
				upd(stk[tp--], -1);
			}
			upd(stk[++tp] = x, 1);
		}
	cout << ans << '\n';
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details