Tìm một hoán vị sao cho số chỉ số mà gcd (p [i], i)> 1 chính xác là K trong C ++

Giả sử chúng ta có hai số nguyên N và K. Chúng ta phải tìm một hoán vị của các số nguyên trong phạm vi [1 đến N] sao cho số chỉ số (1 - lập chỉ mục cơ sở) trong đó gcd (P [i], i)> 1 là chính xác K. Vì vậy, nếu N =4 và K =3, thì đầu ra sẽ là [1, 2, 3, 4], như gcd (1, 1) =1, gcd (2, 2) =2, gcd (3, 3) =3, gcd (4, 4) =4

Nếu quan sát kỹ, chúng ta có thể thấy rằng gcd (i, i + 1) =1, gcd (1, i) =1 và gcd (i, i) =i. Vì GCD của bất kỳ số nào và 1 luôn là 1, K gần như có thể là N - 1. Xét hoán vị trong đó P [i] =i. Số chỉ số trong đó gcd (P [i], i)> 1, sẽ là N - 1. Nếu chúng ta hoán đổi hai phần tử liên tiếp không bao gồm 1, sẽ làm giảm số lượng các chỉ số đó chính xác là 2 và hoán đổi với 1 sẽ giảm số lượng chính xác là 1.

Ví dụ

#include<iostream>
using namespace std;
void findPermutation(int n, int k) {
   if (k >= n || (n % 2 == 0 && k == 0)) {
      cout << -1;
      return;
   }
   int P[n + 1];
   for (int i = 1; i <= n; i++)
   P[i] = i;  
   int count = n - 1;
   for (int i = 2; i < n; i+=2) {
      if (count - 1 > k) {
         swap(P[i], P[i + 1]);
         count -= 2;
      } else if (count - 1 == k) {
         swap(P[1], P[i]);
         count--;
      } else
         break;
   }
   for (int i = 1; i <= n; i++)
   cout << P[i] << " ";
}
int main() {
   int n = 5, k = 3;
   cout << "Permutation is: ";
   findPermutation(n, k);
}

Đầu ra

Permutation is: 2 1 3 4 5