#P13376. [ABC230G] GCD Permutation

    ID: 12560 传统题 5000ms 888MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>CF2400数论莫比乌斯反演数学组合数学筛法

[ABC230G] GCD Permutation

AT_abc230_g [ABC230G] GCD Permutation

题目描述

给定一个 11 到 NN 的整数的排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N)。

请你计算满足 1≤i≤j≤N1\leq i\leq j\leq N,且同时满足 GCD(i,j)≠1GCD(i,j)\neq 1 且 GCD(Pi,Pj)≠1GCD(P_i,P_j)\neq 1 的整数对 (i,j)(i,j) 的个数。
其中,对于正整数 xx,yy,GCD(x,y)GCD(x,y) 表示 xx 和 yy 的最大公约数。

输入格式

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

NN P1P_1 P2P_2 …\ldots PNP_N

输出格式

输出答案。

输入输出样例 #1

输入 #1

6
5 1 3 2 4 6

输出 #1

6

输入输出样例 #2

输入 #2

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

输出 #2

32

说明/提示

限制条件

  • 1≤N≤2×1051 \leq N \leq 2\times 10^5
  • (P1,P2,…,PN)(P_1,P_2,\ldots,P_N) 是 (1,2,…,N)(1,2,\ldots,N) 的一个排列。
  • 输入均为整数。

样例解释 1

满足条件的组有 (3,3)(3,3)、(3,6)(3,6)、(4,4)(4,4)、(4,6)(4,6)、(5,5)(5,5)、(6,6)(6,6) 共 66 个。因此,输出 66。