← 返回题目列表

Codeforces · 2045/K

K. 最大公约数差分图

中文机器翻译题面 查看原题

您正在玩最大公约数牌组构牌游戏 (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

3
3 3 3

输出 #1

36

输入 #2

4
2 2 4 4

输出 #2

44

输入 #3

9
4 2 6 9 7 7 7 3 3

输出 #3

10858

注意

示例输入/输出#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$$$ 构建两套牌的方法。