← 返回题目列表

AtCoder · abc230_g

G. GCD 排列

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

分数: 600 点

问题陈述

给定是一个排列 P=(P_1,P_2,\ldots,P_N) 中的整数 1 通过 N.

查找整数对的数量 (i,j) 这样 1\leq i\leq j\leq N 满意 GCD(i,j)\neq 1 和 GCD(P_i,P_j)\neq 1.
这里,对于正整数 x 和 y, GCD(x,y) 表示最大公约数 x 和 y.

约束

  • 1 \leq N \leq 2\times 10^5
  • (P_1,P_2,\ldots,P_N) 是一个排列 (1,2,\ldots,N).
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
P_1 P_2 \ldots P_N

输出

打印答案。


示例输入 1

6
5 1 3 2 4 6

示例输出 1

6

六对 (3,3), (3,6), (4,4), (4,6), (5,5), (6,6) 满足条件,所以 应打印 6 。


示例输入 2

12
1 2 3 4 5 6 7 8 9 10 11 12

示例输出 2

32