75A - Жизнь без нулей

This is a "straightforward-implementation" problem. Eliminate all the zeros in each integer and check whether the sum equation still holds or not.

75B - Стена Facetook

The main issue involved in this problem is how to correctly sort out the names and actions. After this, we only need to record the scores that every user can obtain, and output them in the required order.

75C - Модифицированный НОД

At first, we should compute the GCD of the given two integers. As their common divisors must also be the divisors of GCD, the next step is to calculate all the divisors of GCD, and store them in the array S. Then, we sort S in a decreasing order, and for each query, we can directly enumerate S from the last element to the first one while stopping if we find the first element that falls into the interval.

It seems that the above algorithm might lead to a risk of TLE. However, it turns out that the number of divisors of GCD cannot be very large, even if the maximum integer is up to 1E+9. Suppose that one integer only has 2 as its prime divisor. Then, it cannot exceed 2^36, and thus the number of divisors is at most 37. If it has 2 and 3 as its prime diviosrs, the number turns out to be at most 18*18. Furthermore, if it has 2, 3 and 5, the number seems to be less than 10^3. According to these observations, the above enumeration algorithm almost surely works well.

75D - Максимальная сумма

A well designed problem! We should first implement some pre-calculation before solving it. For the i-th small array a[n], we compute its total sum T[i], the maximum prefix sum P[i], the maximum suffix sum S[i] and the maximum sum of sub-sequence M[i].

For the large array b[m], we use b_end[m] to denote the maximum sum with b[j] as the ending. This can be calculated by the following formula:

1）if b_end[j-1]+T[b[j]]>S[b[j]], then b_end[j]=b_end[j-1]+T[b[j]]

2）otherwise b_end[j]=S[b[j]]

with b_end[0] initialized as S[b[0]].

Then, we enumerate b_end[m] and find out the maximum b_end[j]+P[j]. Note that we should further compare this value with all the M[j] that have appeared in b[m], and find out the maximum one as the final answer.