#P13675. [ARC136E] Non-coprime DAG

    ID: 12877 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-最小质因子预处理埃氏筛区间求交差分标记区间修改扫描线

[ARC136E] Non-coprime DAG

题目描述

有一个包含 NN 个顶点的有向图 GG,顶点编号为 11 到 NN。

对于任意两个顶点 i,ji, j(1≤i,j≤N1 \leq i, j \leq N,i≠ji \neq j),当且仅当同时满足以下两个条件时,存在一条从 ii 到 jj 的有向边 i→ji \to j:

  • i<ji < j
  • gcd(i,j)>1\mathrm{gcd}(i, j) > 1

此外,每个顶点都有一个确定的价值,顶点 ii 的价值为 AiA_i。

请你选择一个顶点集合 ss,使其满足以下条件:

  • 对于 ss 中任意两个不同的顶点对 (x,y)(x, y)(x<yx < y),在图 GG 上都无法从 xx 到 yy 到达。

请你求出 ss 中所有顶点的价值之和的最大可能值。

输入格式

输入通过标准输入给出,格式如下:

NN A1A_1 A2A_2 ⋯\cdots ANA_N

输出格式

请输出答案。

输入输出样例 #1

输入 #1

6
1 1 1 1 1 1

输出 #1

4

输入输出样例 #2

输入 #2

6
1 2 1 3 1 6

输出 #2

8

输入输出样例 #3

输入 #3

20
40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3

输出 #3

343

说明/提示

限制条件

  • 1≤N≤1061 \leq N \leq 10^6
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • 所有输入的值均为整数

样例解释 1

可以选择 s={1,2,3,5}s = \{1, 2, 3, 5\}。

样例解释 2

可以选择 s={1,5,6}s = \{1, 5, 6\}。

由 ChatGPT 4.1 翻译