P15678 [ICPC 2024 Jakarta R] GCDDCG

你正在玩 最大公约数牌组构建游戏（GCDDCG）。游戏中有 $N$ 张卡牌（编号从 $1$ 到 $N$）。第 $i$ 张卡牌有一个值 $A_i$，它是一个介于 $1$ 到 $N$（含）之间的整数。 游戏包含 $N$ 轮（编号从 $1$ 到 $N$）。在每一轮中，你需要构建两个非空的牌堆：牌堆 $1$ 和牌堆 $2$。一张卡牌不能同时属于两个牌堆，并且允许不使用所有 $N$ 张卡牌。在第 $i$ 轮中，每个牌堆中卡牌值的**最大公约数 (GCD)** 必须等于 $i$。 你在第 $i$ 轮的**创造力点数**是 $i$ 与构建两个有效牌堆的**方案数**的乘积。如果两个方案中有一个牌堆包含的卡牌不同，则认为它们是不同的方案。 请计算所有 $N$ 轮的创造力点数之和。由于总和可能非常大，请将结果对 $998\,244\,353$ 取模后输出。

第一行包含一个整数 $N$（$2 \leq N \leq 200\,000$）。 第二行包含 $N$ 个整数 $A_i$（$1 \leq A_i \leq N$）。

输出一个整数，表示所有 $N$ 轮的创造力点数之和模 $998\,244\,353$ 的结果。

**样例输入/输出 #1 的解释** 第 $1$ 轮和第 $2$ 轮的创造力点数均为 $0$。 在第 $3$ 轮中，构建两个牌堆共有 $12$ 种方案。记 $B$ 和 $C$ 分别为牌堆 $1$ 和牌堆 $2$ 中的卡牌编号集合。构建两个牌堆的 $12$ 种方案如下： - $B = \{ 1 \}, C = \{ 2 \}$； - $B = \{ 1 \}, C = \{ 3 \}$； - $B = \{ 1 \}, C = \{ 2, 3 \}$； - $B = \{ 2 \}, C = \{ 1 \}$； - $B = \{ 2 \}, C = \{ 3 \}$； - $B = \{ 2 \}, C = \{ 1, 3 \}$； - $B = \{ 3 \}, C = \{ 1 \}$； - $B = \{ 3 \}, C = \{ 2 \}$； - $B = \{ 3 \}, C = \{ 1, 2 \}$； - $B = \{ 1, 2 \}, C = \{ 3 \}$； - $B = \{ 2, 3 \}, C = \{ 1 \}$； - $B = \{ 1, 3 \}, C = \{ 2 \}$。 **样例输入/输出 #2 的解释** 对于第 $1$、$2$、$3$ 和 $4$ 轮，构建两个牌堆的方案数分别为 $0$、$18$、$0$ 和 $2$。 翻译由 DeepSeek V3.2 完成