Find the largest LCM(E)
Time Limit:4S Memory Limit:5120K
Description
I believe that most of you know how to split a positive integer N into the sum of several positive integers, such that their product is the biggest. We only shall try best to split N into the sum of multiple 3.
Then, how about splitting N such that their Least Common Multiplier (LCM) is the biggest?
Input
Input contains several test cases.
Each case has only one line, consisting of two positive integers, N and M. (0 < N <= 3000, 0 < M <= 10000)
The last case is followed by a line containing two zeros.
Output
The output for each case contains the biggest LCM's mod M.
Sample Input
6 23
6 23
0 0
Sample Output
Case 1: 6
Case 2: 6
Strange Machine(F)
Time Limit:10S Memory Limit:32768K
Description
One Day, you find the neighbor girl gets a magic machine! When pressing the green button, the two bulbs above will flash by turns; when pressing the red buttons, the machine will make a precise movement forward. What excites the girl most is that the machine can quickly calculate how many pairs of poker cards are not put in such order that the bigger number is under the smaller one. So, when you put some down cards with number on each card before the machine, and press the green and red buttons at the same time, it will quickly run ahead and write down exactly how many pairs of cards are in wrong order! You ask the girl how she gets this machine. She always says that a smiling handsome guy with green hair gives her the gift in her dream, and she wakes up with the machine in her hands.
You are unwilling to show weakness and claim that such number, called 'inversion pair', is easy to calculate, and there is a whole set of algorithms, such as merging algorithm, to deal with such problems. However, when the girl tells you that the machine's result will change quickly and exactly as soon as you switch the order of the two cards, you blush and promise her for a simulation program...Now is the time for you to keep your promise.
Input
Input contains several cases.
For each case, the first line contains two numbers, specifying that there are n poker cards and m times of switch(1 <= n <= 10^5, 1 <= m <= 10^5). The second line contains n numbers, specifying the number in each poker card from up to down. The number ranges from 0 to 100,000. There are m lines followed, each line contains 2 numbers, specifying the rank number of the two switch cards from up to down.
Input ends with a zero.
Output
For each case, you should first output how many inversion pairs in the initial pile of poker cards, then output the number of inversion pairs after each switch.
Sample Input
2 1
1 2
1 2
10 5
2 5 8 7 6 1 9 4 10 3
1 6
3 9
2 10
4 5
8 6
0
Sample Output
Case 1:
0
1
Case 2:
20
19
22
19
18
19
