# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The city of Dhaka is experiencing the construction of metro rails. Imagine one such metro rail spans from Gulshan to Mirpur. There will be N blocks in total that will serve as the holding structure for the rail lines. The first block is numbered as 1 and the final block is numbered as N. Construction process is fast and each day, one block is being created. But there is a problem.

The blocks are not constructed sequentially. For example, if N=5, the blocks can be created in the following order: 2,4,5,3,1. Since the orders are random, the construction company wants to keep track of the progress properly. They want to measure how many contiguous blocks are created from the start after each day’s work.

You will be given the order of blocks in which they are going to be constructed. You have to answer after each day, maximum size of contiguous blocks that are made **from the start**. The first block is identified as 1.

For this problem, you need an integer N and a permutation of 1 to N as an array A of size N. the i^{th} integer represents the block constructed on i^{th} day. Since N can be very big, we will provide two integers g and N.
Then you will construct the array as **A _{i} = g^{i-1} mod (N+1), where (1 ≤ i ≤ N)**.

There will be two integers g and N as input.

**3 ≤ N ≤ 100000000****2 ≤ g < N**

Calculate N integers. The i^{th} integer indicates the number of contiguous blocks are made from the start after the i^{th} day. Now print the XOR value of these integers. If the integers are considered an array B_{1}, B_{2}, … B_{N}, then print (B_{1} xor B_{2} … xor B_{N}).

Input | Output |
---|---|

3 6 | 2 |

Input | Output |
---|---|

8 10 | 9 |

For the first sample, the array A = [1 3 2 6 4 5]

On the 1st day, Block 1 is built. So, the size from the start, B_{1} = 1.

On the 2nd day, Block 3 is built. So, the size from the start, B_{2} = 1. (1 and 3 are not connected)

On the 3rd day, Block 2 is built. B_{3} = 3.

On the 4th day, Block 6 is built. B_{4} = 3.

On the 5th day, Block 4 is built. B_{5} = 4.

On the 6th day, Block 5 is built. B_{6} = 6.

So, the XOR of all the values is 2.

53% Solution Ratio

EgorKulikovEarliest,

avijit_agarwalFastest, 0.6s

hp1999Lightest, 131 kB

kzvd4729Shortest, 339B

Login to submit

Criterion 2020 Round 4 Ended |