PROBLEM LINK:
Practice
Contest, div. 1
Contest, div. 2
Author: Sumit Jain
Tester: Zhong Ziqian
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY
PREREQUISITES:
Euclid’s algo, DFS
PROBLEM:
You’re given rooted tree with N nodes. Each node has value v_i and parameter m_i. Let denote leafs of the tree as l_1,\dots,l_L in icreasing order. For each leaf l_i you have to find answer a_i which is defined as maximum possible remainder modulo m_{l_i} of some integer linear combination of values of the vertices on the path from l_i to the root.
QUICK EXPLANATION:
For each leaf you should output m_{l_i}-\gcd(g,m_{l_i}) where g is \gcd of all values on the path from the leaf to the root.
EXPLANATION:
Since we consider only integer linear combinations, we may prove that arbitrary number x may be obtained as linear combination of v_1, \dots, v_k if and only if it’s divisible by g=\gcd(v_1,\dots,v_k).
It’s proven by induction: for k=2 it’s true because any linear combination is divisible by g and we always may find linear combination which is equal to g by extended Euclid’s algorithm. This means that if we consider triple (v_1,v_2,v_3) we may actually substitute pair (v_1,v_2) by single number which is equal to \gcd(v_1,v_2), then we substitute (\gcd(v_1,v_2),v_3) with single number \gcd(v_1,v_2,v_3) for the same reason. In this manner it may be proven for arbitrary k.
Now if we consider single number g (which is equal to \gcd of all values on the path to the root) what’s the largest remainder modulo m we can obtain among numbers g, 2g, 3g, \dots? All of these numbers are divisible by g'=\gcd(g,m). Moreover, one of them is equal to g'! Indeed, let’s look on diophantine equation k_1g=g'+k_2m. Since both g and m are divisible by g', we may reduce the whole equation by it so we will have k_1\tfrac{g}{g'}-k_2\tfrac{m}{g'}=1 and since \tfrac{g}{g'} and \tfrac{m}{g'} are co-prime, this equation will always have a solution. Thus we may substitute g with g' and after that we may immediately say what’s the largest remainder of kg' modulo m. Since m is divisible by g' the answer is simply m-g'.
Knowing that fact, we may solve the problem by simple depth-first search if we will calculate \gcd of all values from the root to the current node in it. This will solve the problem in O(N \log C):
void dfs(int v = 1, int p = 1, int G = val[1]) {
for(auto u: g[v]) {
if(u != p) {
dfs(u, v, __gcd(G, val[u]));
}
}
if(g[v].size() == 1 && v != 1) {
ans[v] = mod[v] - __gcd(mod[v], G);
}
}
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.