[Solution] Perfect Permutation solution codechef

Perfect Permutation solution codechef – An index ii in a permutation PP of length NN is said to be good if:

  • PiPi is divisible by ii

You are given 22 integers NN and KK. You need to construct a permutation PP of length NN such that exactly KK indices in that permutation are good.

If no such permutation exists, output 1−1.

If multiple such permutations exist, output any.

Perfect Permutation solution codechef

  • The first line contains a single integer TT – the number of test cases. Then the test cases follow.
  • The first and only line of each test case contains two integers NN and KK – the length of the permutation to be constructed and the number of good indices.

Output Format

For each test case, output any permutation satisfying the given condition.

Perfect Permutation solution codechef

  • 1T10001≤T≤1000
  • 1N1051≤N≤105
  • 1KN1≤K≤N
  • Sum of NN over all testcases does not exceed 21052⋅105

Sample Input 1 

1 1
6 2

Perfect Permutation solution codechef


4 5 6 1 2 3


Test case-1: In [1][1]P1=1P1=1 is divisible by 11. Therefore it is a valid permutation having 11 good index.

Test case-2: In [4,5,6,1,2,3][4,5,6,1,2,3]P1=4P1=4 is divisible by 11 and P3=6P3=6 is divisible by 33. Therefore it is a valid permutation having 22 good indices.

Leave a Comment