Div2-A

Create an array used of 100 elements. i-th element for the segment (i, i + 1).

For every student except Alexey set used[i]  =  true for each segment (i,  i  +  1) in the segment of that student. After that for each subsegment (i,  i  +  1) of Alexey's segment add 1 to result if used[i]  =  false.

Div2-B

First of all, calculate how many L's we can bring so that the result will not exceed N. It's .

Now, if R·K  ≥  N we may increase any of K numbers by 1. At some moment sum will be equal to N becase sum of K R's is greater than N. So answer in this case is YES.

If R·K  <  N, we can't get K or less numbers because their sum is less than N. But we can't get more than K numbers too, because their sum is more than N. So answer is NO.

Complexity: O(1) for every query. Overall complexity: O(t).

Div1-A/Div2-C

Let's factorize all n numbers into prime factors. Now we should solve the problem for every prime independently and multiply these answers. The number of ways to split p^k into n multipliers, where p is prime, is equal to C(k  +  n  -  1,  n  -  1) (it can be obtained using the method of stars and bars, you can read about it here, choose 'combinatorics'). So we have a solution that needs time.

Div1-B/Div2-D

First of all, let's consider n  +  1  =  p is prime. Then we can prove by induction that the answer is . Base for p  =  3 is obvious. If this equality holds for p, and q is the next prime, then answer for q is equal to answer for p plus q  -  p equal summands , that is , that's we wanted to prove.

Next using that the distance between two consecutive primes not exceeding 10⁹ does not exceed 300, we can find the answer as a sum of the answer for the maximal prime not exceeding n and several equal summands . We see that the denominator is a divisor of 2pq, which fits in long long.

Div1-C/Div2-E

We can write all vertices in the list in order of dfs, then the descendants of the vertex from a segment of this list. Let's count for every vertex its distance to the root level[v].

Let's create two segment trees st1 and st2. If we are given a query of the first type, in st1 we add x  +  level[v]·k to the segment corresponding to the vertex v, in st2 we add k to the segment corresponding to the vertex v.

If we are given a query of the second type, we write st1.get(v) - st2.get(v) * level[v].

The complexity is O(qlogn).

You can use any other data stucture that allows to add to the segment and to find a value of an arbitrary element.

Also there exists a solution using Heavy-Light decomposition.

Div1-D

Let's prove a useful fact: sum of number of invertions for all permutations of size k is equal to . The prove is simple: let's change in permutation p for every i p_i to k  +  1  -  p_i. Then the sum of number of invertions of the first and the second permutations is , and our conversion of the permutation is a biection.

Now we suppose that we are given a permutation of numbers from 0 to n  -  1.

Let's go at p from left to right. What permutations are less than p?

• Permutations having first number less than p₀. If the first number is a  <  p₀, than in every such permutation there are a inversions of form (first element, some other element). So in all permutations beginning with a there are a·(n  -  1)! inversions of this from. Moreover, there are inversions not including the first element, their sum is sumAll[n  -  1]. Then, counting sum for all a we have inversions.
• Permutations beginning with p₀. At first, we should count the number of inversions, beginning in p₀. There are cnt·p₀ of this form, where cnt is the number of permutations beginning with p₀ and not exceeding p. Then we should count the inversions not beginning in the beginning. But it is the same problem! The only exception is that if

  Unable to parse markup [type=CF_TEX]

  , there are p₁  -  1 available numbers less than p₁, but not p₁. So we get a solution: go from left to right, keep already used numbers in Fenwick tree, and then solve the same problem, assuming that the first number is not p_i but p_i - (the number of used numbers less than p_i).

The last we should do is to count the number of permutations not exceeding the suffix of p and beginning the same. It can be precomputed, if we go from right to left. In this case we should do the same as in the first part of solution, but consider that the minimal number is a number of already used numbers less than current.

Div1-E

We will describe an algorithm and then understand why it works.

For every prime we will maintain a list of intervals. At the first moment for every p_i we add in its list interval [0;a_i), other primes have an empty list.

Then we go from big primes to small. Let's consider that current prime is p. If in its list there exists an interval [x;y), $x < k, y > k$, we divide it into two parts [x;k) and [k;y).

Then for every interval [x;y), x  ≥  k (in fact, in this case x  =  k) we add to the answer for p y  -  x. For intervals, where y  ≤  k, we add to list of every prime divisor of p  -  1 invterval [x  +  1,  y  +  1). If p  -  1 has some prime if more than first power, we should add this segment several times.

After that we should conduct a "union with displacement" operation for every prime which list was changed. If in one list there are 2 invervals [x,  y), [z,  t) so that y  ≤  z  >  x, we replace them with one interval [x,  y  +  t  -  z) (so we added t  -  z to the right border of the first interval). Then we go to next (lesser) p.

Why does it works? If we take function φ one time, for every prime p which divides n, n is divided by p and multiplied by p  -  1 (or, the same, by all prime divisors p  -  1 in corresponding powers).

Now we can observe that intervals in lists contains the numbers of iterations, when the number contains the corresponding prime number. Bigger primes do not affect smaller, so we can process them earlier. If after i-th iteration the number contains prime number p, after i  +  1-th iteration it contains prime divisors of p  -  1, and we add segments in accordance with this. The k-th iteration is the last, so the existence of the interval [k,  x) means that after k-th iteration we have (x  -  k)-th power of this prime. From this it is clear why we unite the intervals if that way.

Why does it work fast?

1. Because we precalculated the minimal prime divisor of each number up to MAXPRIME using linear Eratosthenes sieve. (Well, it's not necessary)

2. Because for each prime there's no more than intervals, because for each [a,  b) range . Practically there is no more than 6 segments at once.

Any questions about the editorial are welcome! Especially the English one :)

This post was restored from google cache, and I have edited formula once again. If you notice some mistake, please send be a private message.