「CF1285F」Classical - 数论 + 栈

给出一个长度为$n$的数组$a_i$, 求

$\max\limits_{1 \le i < j \le n} LCM(a_i,a_j)$

$n \le 10^5, a_i \le 10^5$

Link

CF1285H

Pre-knowledge

维护一个集合$S$，支持下列操作:

1. 插入/删除一个数$x$

2. 查询集合中与$x$互质的数有多少个

每个操作的复杂度需均为$O\Big(\sigma_0(x)\Big)$

---

化式子，查询即要求:

$\begin{aligned} &\sum_{y \in S} [(x, y) == 1] \\ = &\sum_{y \in S} \sum_{d|x, d|y} \mu(d)\\ = &\sum_{y \in S} \sum_{d|x} \mu(d)\cdot [d | y]\\ = &\sum_{d|x} \mu(d)\cdot \sum_{y \in S} [d | y]\\ = &\sum_{d|x} \mu(d)\cdot cnt(d)\\ \end{aligned}$

其中$cnt(d)$表示集合中$d$的倍数的数的个数，显然$cnt(d)$可以在插入/删除时通过枚举约数维护，答案也可以直接枚举约数计算

所有操作的复杂度均为$O\Big(\sigma_0(x)\Big)$

Solution

$\displaystyle LCM(a_i, a_j) = \frac{a_i a_j}{\gcd (a_i, a_j)}$，显然枚举$g$，计算$(a_i, a_j) = g$的所有$i, j$中，$a_ia_j$的最大值

首先可以$O(n \ln n)$直接枚举$g$的所有倍数$x$，然后判断原序列中是否存在$x$。这样可以得到一个新的序列$b_i$，题目便转化为在$b$中找到一对$i, j$，使得$(b_i, b_j) = 1$，且$b_ib_j$最大

考虑如何将 Pre-knowledge 中的数据结构派上用场

将$b$数组降序排列，维护一个栈。设当前数字为 $x$ ，只要栈中存在与 $x$ 互质的数，就拿栈顶与 $x$ 的乘积更新 $ans$ ，然后弹掉栈顶，循环如此，最后把 $x$ 入栈。因为比 $x$ 更小的数乘上栈顶一定不优，而若栈顶与 $x$ 并不互质，这样得到的值也一定会被覆盖掉，所以正确性是对的。

总复杂度$\displaystyle O\big(\sum_{i=1}^{n}\sigma_0^2(i)\big)$

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1e5;

int N = MAXN, A[MAXN + 5], Mu[MAXN + 5];

vector <int> G[MAXN + 5]; 

inline void Init ()
{
	for (int i = 1; i <= N; ++i) 
		for (int j = i; j <= N; j += i)
			G[j].pb (i);

	static bitset <MAXN + 5> Vis;
	static int prime[MAXN + 5];

	Mu[1] = 1;
	for (int i = 2; i <= N; ++i) 
	{
		if (!Vis[i])
		{
			prime[++prime[0]] = i;
			Mu[i] = -1;
		}

		for (int j = 1; j <= prime[0] && (LL) i * prime[j] <= N; ++j)
		{
			Vis[i * prime[j]] = 1;
			if (!(i % prime[j]))
			{
				Mu[i * prime[j]] = 0;
				break;
			}
			Mu[i * prime[j]] = -Mu[i];
		}
	}
}

namespace DS
{
	int cnt[MAXN + 5];

	inline void insert (int x) { for (int y : G[x]) ++cnt[y]; }
	
	inline void erase (int x) { for (int y : G[x]) --cnt[y]; }

	inline int query (int x)
	{
		int ans = 0;
		for (int y : G[x]) ans += Mu[y] * cnt[y];
		return ans;
	}
}

LL ans;

inline void Solve ()
{
	Init ();
	
	for (int g = 1; g <= N; ++g)
	{
		static vector <int> vec; 
		for (int i = g; i <= N; i += g) if (A[i]) vec.pb (i / g);

		if (vec.size() == 0) continue;

		static int stk[MAXN + 5], top;

		for (int i = vec.size() - 1; i >= 0; --i)
		{
			while (top && DS :: query (vec[i])) Chkmax (ans, (LL) g * vec[i] * vec[stk[top]]), DS :: erase (vec[stk[top]]), --top;
			stk[++top] = i, DS :: insert (vec[i]);
		}

		while (top) DS :: erase (vec[stk[top]]), --top;
		vec.clear();
	}

	cout << ans << endl;
}

inline void Input ()
{
	int n = read<int>();
	while (n--)
	{
		int x = read<int>();
		A[x] = 1;
		Chkmax (ans, (LL) x);
	}
}

int main ()
{

#ifdef hk_cnyali
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}