#P22504. [ABC230G]GCD Permutation
[ABC230G]GCD Permutation
题目链接
题意
已知一个长度为 的排列 。
求有多少对数 ,满足 且 且 。
输入格式
第一行一个整数 。
第二行 个整数,表示排列 。
输出格式
一行一个数,表示答案。
样例
6
5 1 3 2 4 6
6
12
1 2 3 4 5 6 7 8 9 10 11 12
32
数据范围
已知一个长度为 n 的排列 p。
求有多少对数 (i,j),满足 1≤i≤j≤n 且 gcd(i,j)=1 且 gcd(pi,pj)=1。
第一行一个整数 n。
第二行 n 个整数,表示排列 p。
一行一个数,表示答案。
6
5 1 3 2 4 6
6
12
1 2 3 4 5 6 7 8 9 10 11 12
32
1≤n≤2×105