SRM 703 GCDGraph

class GCDGraph {
public:
    string possible(int n, int k, int x, int y) {
        vector<int> tree(n + 1, 0);
        std::iota(tree.begin(), tree.end(), 0);
        std::function<int(int)> root = [&] (int i) {
            if (tree[i] != i) {
                // Tail recursion is surprisingly well optimized
                // here by compiler to pass large test data set.
                tree[i] = root(tree[i]);
            }
            return tree[i];
        };
        
        for (int i = k + 1; i <= n; ++i) {
            int r = root(i);
            for (int j = i + i; j <= n; j += i) {
                tree[root(j)] = r;
            }
        }
        
        return root(x) == root(y) ? "Possible" : "Impossible";
    }
}