这里是关于CodeForce Round 554 Div 2的一些题解

# A. Neko Finds Grapes

## Problem

On a random day, Neko found $n$ treasure chests and $m$ keys. The $i^{th}$ chest has an integer $a_i$ written on it and the $j^{th}$ key has an integer $b_j$ on it. Neko knows those chests contain the powerful mysterious green Grapes, thus Neko wants to open as many treasure chests as possible.

The $j^{th}$ key can be used to unlock the $i^{th}$ chest if and only if the sum of the key number and the chest number is an odd number. Formally, $a_i+b_j \equiv 1(mod2)$. One key can be used to open at most one chest, and one chest can be opened at most once.

Find the maximum number of chests Neko can open.

## Input

The first line contains integers $n$ and $m$ $(1 \leq n,m \leq 10^5)$ — the number of chests and the number of keys.

The second line contains $n$ integers $a_1,a_2,…,a_n (1 \leq a_i \leq 10^9)$ — the numbers written on the treasure chests.

The third line contains $m$ integers $b_1,b_2,…,b_m (1 \leq b_i \leq 10^9)$ — the numbers written on the keys.

## Output

Print the maximum number of chests you can open.

## Example

input

5 4

9 14 6 2 11

8 4 7 20output

3

input

5 1

2 4 6 8 10

5output

1

input

1 4

10

20 30 40 50output

0

## Note

In the first example, one possible way to unlock 3 chests is as follows:

Use first key to unlock the fifth chest,

Use third key to unlock the second chest,

Use fourth key to unlock the first chest.

In the second example, you can use the only key to unlock any single chest (note that one key can’t be used twice).

In the third example, no key can unlock the given chest.

## 想法

暴力出奇迹，奇偶配对

## The Code Of My Program

1 | /********************* |

# B. Neko Performs Cat Furrier Transform

## Problem

Cat Furrier Transform is a popular algorithm among cat programmers to create longcats. As one of the greatest cat programmers ever exist, Neko wants to utilize this algorithm to create the perfect longcat.

Assume that we have a cat with a number $x$. A perfect longcat is a cat with a number equal $2^m−1$ for some non-negative integer $m$. For example, the numbers $0, 1, 3, 7, 15$ and so on are suitable for the perfect longcats.

In the Cat Furrier Transform, the following operations can be performed on $x$:

(Operation A): you select any non-negative integer $n$ and replace $x$ with $x⊕(2^n−1)$, with $⊕$ being a bitwise $XOR$ operator.

(Operation B): replace $x$ with $x+1$.

The first applied operation must be of type $A$, the second of type $B$, the third of type $A$ again, and so on. Formally, if we number operations from one in the order they are executed, then odd-numbered operations must be of type $A$ and the even-numbered operations must be of type $B$.

Neko wants to produce perfect longcats at industrial scale, thus for each cat Neko only wants to perform at most 40 operations. Can you help Neko writing a transformation plan?

Note that it is not required to minimize the number of operations. You just need to use no more than 40 operations.

## Input

The only line contains a single integer $x (1 \leq x \leq 10^6)$.

## Output

The first line should contain a single integer $ t (0 \leq t \leq 40) $ — the number of operations to apply.

Then for each odd-numbered operation print the corresponding number $n_i$ in it. That is, print $\left \lceil \frac{t}{2} \right \rceil$ integers $n_i (0 \leq n_i \leq 30)$, denoting the replacement $x$ with $x⊕(2^{n_i}−1)$ in the corresponding step.

If there are multiple possible answers, you can print any of them. It is possible to show, that there is at least one answer in the constraints of this problem.

## Example

input

39

output

4

5 3input

1

output

0

input

7

output

0

## Note

In the first test, one of the transforms might be as follows: 39→56→57→62→63. Or more precisely:

Pick n=5. x is transformed into 39⊕31, or 56.

Increase x by 1, changing its value to 57.

Pick n=3. x is transformed into 57⊕7, or 62.

Increase x by 1, changing its value to 63=26−1.

In the second and third test, the number already satisfies the goal requirement.

## 想法

按照题目模拟即可

## The Code Of My Program

1 | /********************* |

# C. Neko does Maths

## Problem

Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.

Neko has two integers $a$ and $b$. His goal is to find a non-negative integer $k$ such that the least common multiple of $a+k$ and $b+k$ is the smallest possible. If there are multiple optimal integers $k$, he needs to choose the smallest one.

Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?

## Input

The only line contains two integers $a$ and $b (1 \leq a,b \leq 109)$.

## Output

Print the smallest non-negative integer $k (k \leq 0)$ such that the lowest common multiple of $a+k$ and $b+k$ is the smallest possible.

If there are many possible integers $k$ giving the same value of the least common multiple, print the smallest one.

## Examples

input

6 10

output

2

input

21 31

output

9

input

5 10

output

0

## Note

In the first test, one should choose $k=2$, as the least common multiple of $6+2$ and $10+2$ is $24$, which is the smallest least common multiple possible.

## 想法

这题题意是找出一个$k$，使得$lcm(a+k,b+k)$最小

首先你要知道$lcm(a,b)=\frac{a \times b }{ gcd(a,b)}$

The $lcm(a+k,b+k)$ is equal to $\frac{(a+k)\times(b+k)}{gcd(a+k,b+k)}$. In fact, there are not much possible values for the denominator of this fraction.

Without losing generality, let’s assume $a \leq b$. Applying one step of Euclid’s algorithm ($gcd(a,b)=gcd(b−a,a)$) we can see, that $gcd(a+k,b+k)=gcd(b−a,a+k)$.

So the $gcd$ is a divisor of $b−a$. Let’s iterate over all divisors $q$ of $b−a$. That also means that $a(modq)=b(modq)$. In case $a(modq)=0$, we can use $k=0$. Otherwise, the corresponding $k$ should be $q−a(modq)$. Lastly, we need to check whether the value of $lcm(a+k,b+k)$ is the smallest found so far.

Also, one has to be careful when dealing with $k=0$ answer, which was the reason why many solutions got WA 63.

The complexity is $O(\sqrt{b−a})$.

## The Code Of My Program

1 | /********************* |