CF1016G Appropriate Team

Since next season are coming, you'd like to form a team from two or three participants. There are $ n $ candidates, the $ i $ -th candidate has rank $ a_i $ . But you have weird requirements for your teammates: if you have rank $ v $ and have chosen the $ i $ -th and $ j $ -th candidate, then $ GCD(v, a_i) = X $ and $ LCM(v, a_j) = Y $ must be met. You are very experienced, so you can change your rank to any non-negative integer but $ X $ and $ Y $ are tied with your birthdate, so they are fixed. Now you want to know, how many are there pairs $ (i, j) $ such that there exists an integer $ v $ meeting the following constraints: $ GCD(v, a_i) = X $ and $ LCM(v, a_j) = Y $ . It's possible that $ i = j $ and you form a team of two. $ GCD $ is the greatest common divisor of two number, $ LCM $ — the least common multiple.

N/A

N/A

In the first example next pairs are valid: $ a_j = 1 $ and $ a_i = [2, 4, 6, 8, 10, 12] $ or $ a_j = 2 $ and $ a_i = [2, 4, 6, 8, 10, 12] $ . The $ v $ in both cases can be equal to $ 2 $ . In the second example next pairs are valid: - $ a_j = 1 $ and $ a_i = [1, 5, 7, 11] $ ; - $ a_j = 2 $ and $ a_i = [1, 5, 7, 11, 10, 8, 4, 2] $ ; - $ a_j = 3 $ and $ a_i = [1, 3, 5, 7, 9, 11] $ ; - $ a_j = 6 $ and $ a_i = [1, 3, 5, 7, 9, 11, 12, 10, 8, 6, 4, 2] $ .