CF1101D GCD Counting

You are given a tree consisting of $ n $ vertices. A number is written on each vertex; the number on vertex $ i $ is equal to $ a_i $ . Let's denote the function $ g(x, y) $ as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex $ x $ to vertex $ y $ (including these two vertices). Also let's denote $ dist(x, y) $ as the number of vertices on the simple path between vertices $ x $ and $ y $ , including the endpoints. $ dist(x, x) = 1 $ for every vertex $ x $ . Your task is calculate the maximum value of $ dist(x, y) $ among such pairs of vertices that $ g(x, y) > 1 $ .

N/A

N/A