TheForces Round #17 (AOE-Forces) |
---|
Finished |
You are going to host an Age of Empires tournament, and you want it to be perfect.
There are $$$n$$$ players participating, you let your friends organize the seating of the players and now on the $$$i$$$-th seat from the left sits a player with a rating $$$a_i$$$.
After you thought everything was going perfect, it turns out that you only had cables with length $$$k$$$ that means player $$$i$$$ can play with player $$$j$$$ iff ($$$|j - i| \leq k$$$), and if that wasn't bad enough all the players are elitist, so the player $$$i$$$ will play with player $$$j$$$ iff $$$a_i$$$ and $$$a_j$$$ are coprime.
Given the seating of the $$$n$$$ players and length of the cable $$$k$$$ what is the maximum number of matches can you set up. Note that each player can only participate in one match.
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 10^5; 1 \leq k \leq 8)$$$ – the number of players and the length of the cable.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ – the ratings of the players.
Print a single integer, the answer to the problem.
3 2 1 2 3
1
4 2 1 2 3 5
2
5 1 6 2 2 4 5
1
In the first sample, you could set up the following match: $$$(1, 3)$$$.
In the second sample, this is one of the ways you could set up the matches: $$$(2, 5), (1, 3)$$$.
Name |
---|