#### 450A - Jzzhu и дети

You can simply simulate it or find the last maximum *ceil*(*a* _{ i} / *m*).

#### 450B - Jzzhu и последовательности

We can easily find that every 6 numbers are the same. It's like {*x*, *y*, *y* - *x*, - *x*, - *y*, *x* - *y*, *x*, *y*, *y* - *x*, ...}.

#### 449A - Jzzhu и шоколад / 450C - Jzzhu и шоколад

We assume that *n* ≤ *m* (if *n* > *m*, we can simply swap *n* and *m*).

If we finally cut the chocolate into *x* rows and *y* columns (1 ≤ *x* ≤ *n*, 1 ≤ *y* ≤ *m*, *x* + *y* = *k* + 2), we should maximize the narrowest row and maximize the narrowest column, so the answer will be *floor*(*n* / *x*) * *floor*(*m* / *y*).

There are two algorithms to find the optimal (*x*, *y*).

Notice that if

*x***y*is smaller, the answer usually will be better. Then we can find that if*k*<*n*, the optimal (*x*,*y*) can only be {*x*= 1,*y*=*k*+ 1} or {*x*=*k*+ 1,*y*= 1}. If*n*≤*k*<*m*, the optimal (*x*,*y*) can only be {*x*= 1,*y*=*k*+ 1}. If*m*≤*k*≤*n*+*m*- 2, the optimal (*x*,*y*) can only be {*x*=*k*+ 2 -*m*,*y*=*m*}, because let*t*=*m*-*n*,*n*/ (*k*+ 2 -*m*) ≥ (*n*+*t*) / (*k*+ 2 -*m*+*t*) ≥ 1.*floor*(*n*/*x*) has at most values, so we can enum it and choose the maximum*x*for each value.

#### 449B - Jzzhu и города / 450D - Jzzhu и города

We consider a train route (1, *v*) as an undirected deletable edge (1, *v*).

Let *dist*(*u*) be the shortest path between 1 and *u*. We add all of the edges (*u*, *v*) weighted *w* where *dist*(*u*) + *w* = *dist*(*v*) into a new directed graph.

A deletable edge (1, *v*) can be deleted only if it isn't in the new graph or the in-degree of *v* in the new graph is more than 1, because the connectivity of the new graph won't be changed after deleting these edges. Notice that you should subtract one from the in-degree of *v* after you delete an edge (1, *v*).

#### 449C - Jzzhu и яблоки / 450E - Jzzhu и яблоки

Firstly, we should notice that 1 and the primes larger than *N* / 2 can not be matched anyway, so we ignore these numbers.

Let's consider each prime *P* where 2 < *P* ≤ *N* / 2. For each prime *P*, we find all of the numbers which are unmatched and have a divisor *P*. Let *M* be the count of those numbers we found. If *M* is even, then we can match those numbers perfectly. Otherwise, we throw the number 2*P* and the remaining numbers can be matched perfectly.

Finally, only even numbers may be unmatched and we can match them in any way.

#### 449D - Jzzhu и числа

Firstly, we can use inclusion-exclusion principle in this problem. Let *f*(*x*) be the count of number *i* where *A* _{ i}&x = *x*. Let *g*(*x*) be the number of 1 in the binary respresentation of *x*. Then the answer equals to .

Now the task is to calculate *f*(*x*) for every integer *x* between 0 and 2^{20}. Let *f* _{ k}(*x*) be the count of number *i* where *Y* _{0}&X_{0} = *X* _{0} and *X* _{1} = *Y* _{1} (they are defined below).

We divide *x* and *A* _{ i} into two parts, the first *k* binary bits and the other 20 - *k* binary bits. Let *X* _{0} be the first part of *x* and *X* _{1} be the second part of *x*. Let *Y* _{0} be the first part of *A* _{ i} and *Y* _{1} be the second part of *A* _{ i}.

We can calculate *f* _{ k}(*x*) in *O*(1):

The problem can be solved in *O*(*n* * 2^{ n}) now ( *n* = 20 in this problem).

#### 449E - Jzzhu и квадраты

Consider there is only one query.

Let me descripe the picture above.

A grid-square can be exactly contained by a bigger square which coincide with grid lines. Let *L* be the length of a side of the bigger square. Let *i* be the minimum distance between a vertice of the grid-square and a vertice of the bigger square. Let *f*(*L*, *i*) be the number of cells which are fully contained by the grid-square.

We can divide a grid-square into four right triangles and a center square. For each right triangle, the number of cells which are crossed by an edge of the triangle is *L* - *gcd*(*i*, *L*). Then, the number of cells which are fully contained by the triangle is [*i*(*L* - *i*) - *L* + *gcd*(*i*, *L*)] / 2.

*f*(*L*, *i*) = (*L* - 2*i*)^{2} + 2[*i*(*L* - *i*) - *L* + *gcd*(*i*, *L*)] = *L* ^{2} - 2*iL* + 2*i* ^{2} - 2*L* + 2*gcd*(*i*, *L*)

Firstly, we enum *L* from 1 to *min*(*N*, *M*). Then the task is to calculate . can be calculated by the following steps:

Enum all of the divisor

*k*of*L*and the task is to calculate the count of*i*where*gcd*(*i*,*L*) =*k*.The count of

*i*where*gcd*(*i*,*L*) =*k*equals to φ(*L*/*k*).

Finally, .

If there are multiple queries, we can calculate the prefix sum of , and , then we can answer each query in *O*(1).