/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 以上 N 以下の整数の並び替え P=(P_1,P_2,\ldots,P_N) が与えられます。
1\leq i\leq j\leq N をみたす整数の組 (i,j) であって、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 つです。 よって、 6 を出力します。
入力例 2
12 1 2 3 4 5 6 7 8 9 10 11 12
出力例 2
32
Score : 600 points
Problem Statement
Given is a permutation P=(P_1,P_2,\ldots,P_N) of the integers from 1 through N.
Find the number of pairs of integers (i,j) such that 1\leq i\leq j\leq N satisfying GCD(i,j)\neq 1 and GCD(P_i,P_j)\neq 1.
Here, for positive integers x and y, GCD(x,y) denotes the greatest common divisor of x and y.
Constraints
- 1 \leq N \leq 2\times 10^5
- (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
Print the answer.
Sample Input 1
6 5 1 3 2 4 6
Sample Output 1
6
Six pairs (3,3), (3,6), (4,4), (4,6), (5,5), (6,6) satisfy the condition, so 6 should be printed.
Sample Input 2
12 1 2 3 4 5 6 7 8 9 10 11 12
Sample Output 2
32