#P17266. [2025年南开中学集训]秩序纪元

    ID: 16992 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS有限候选集缩减倍数枚举轮廓线 DP状态维度消除最小公倍数前后缀最值滚动数组

[2025年南开中学集训]秩序纪元

题目描述

混沌散去,序列王国迎来了秩序的黎明。

王国的贤者们以“数能”为基,铸造出一座名为「方阵」的能量矩阵。

这座矩阵是王国的心脏——它由 2×n2\times n 个能量单元构成,第 ii 行第 jj 列的能量为 ai,ja_{i,j}。

然而,为了维持方阵的稳定,贤者们签订了「方阵的契约」——必须将整个矩阵划分成若干个四连通的能量块。对于一个能量块,其强度定义为该块中所有能量值的最小公倍数(LCM)。

整个方阵的紊乱程度则等于所有能量块强度之和。贤者们请求你帮忙计算出最小的方阵紊乱程度。

输入格式

第一行包含一个整数 nn,表示矩阵的大小。

第二行包含 nn 个整数,其中第 ii 个整数表示 a1,ia_{1,i}。

第三行包含 nn 个整数,其中第 ii 个整数表示 a2,ia_{2,i}。

输出格式

输出一行一个整数,表示方阵紊乱程度的最小值。

输入输出样例 #1

输入 #1

6
5 1 9 4 1 14
3 1 10 8 7 9

输出 #1

53

输入输出样例 #2

输入 #2

7
4 8 4 4 4 7 14
12 6 4 4 7 4 2

输出 #2

45

说明 / 提示

数据范围

对于所有数据,保证:

  • 1≤n≤10001\le n\le 1000;
  • 1≤ai,j1\le a_{i,j},且 ∑ai,j≤1018\sum a_{i,j}\le 10^{18}。
子任务编号 分值 限制 特殊性质
1 10 无 A
2 20 n≤30n\le 30 无
3 n≤300n\le 300
4 25 无 B
5 无

特殊性质 A:ai,ja_{i,j} 为 22 的幂。

特殊性质 B:保证存在一种最优划分方案,使得每个连通块的强度均不超过 50005000。

样例解释 #1

具体划分如下图:

所有连通块的 LCM 之和为:3+10+9+8+14+9=533+10+9+8+14+9=53。

样例解释 #2

具体划分如下图:

所有连通块的 LCM 之和为:8+12+7+4+14=458+12+7+4+14=45。