The minimal weight is at least $$$1$$$ since $$$1$$$ divides any integer (so $$$1$$$ divides $$$p_1$$$).

Since $$$k+1$$$ does not divide $$$k$$$, a permutation with weight equal to $$$1$$$ is: $$$[n,1,2,\cdots,n-1]$$$.

See the party as a graph.

Divide the vertices into two categories according to their degrees' parity.

Divide the vertices into two categories according to their degrees' parity.

Let's consider the case where $$$m$$$ is odd only, since if $$$m$$$ is even the answer is $$$0$$$.

Assume that you delete $$$x$$$ vertices with even degrees and $$$y$$$ vertices with odd degrees.

If $$$y \geq 1$$$, then only deleting one vertex with odd degree would have been enough.

If $$$y=0$$$, then the parity of the edges at the end is determined only by the number of edges whose both endpoints are deleted. In particular, there must be at least two adjacent vertices deleted with even degree.

Thus, an optimal solution either has $$$(x, y) = (0, 1)$$$ or $$$(x, y) = (2, 0)$$$ and the two vertices are adjacent.

One can iterate over all possible solutions with such structure and take the optimal one.

Total time complexity: $$$O(n)$$$.