Giả sử chúng ta có hai số nguyên N và K, và chúng ta phải tìm hoán vị P của N số tự nhiên đầu tiên sao cho có đúng K phần tử thỏa mãn điều kiện GCD (P [i], i)> 1 với mọi 1 <=i <=N. Vì vậy, khi N =3 và K =1, thì đầu ra sẽ là 2, 1, 3. Và gcd (2, 1) =1, gcd (1, 2) =1, gcd (3, 3) =3
Cách tiếp cận rất đơn giản, chúng tôi sẽ giữ k phần tử cuối cùng ở vị trí của chúng, phần còn lại được di chuyển, sao cho phần tử thứ i sẽ được đặt ở vị trí thứ (i + 1) và phần tử thứ (N - K) được giữ ở vị trí 1, vì gcd (x, x + 1) =1.
Ví dụ
#include<iostream>
using namespace std;
void findPermutation(int n, int k) {
int permutation[n + 1];
for (int i = 1; i <= n; i++)
permutation[i] = i;
for (int i = 1; i < n - k; i++)
permutation[i + 1] = i;
permutation[1] = n - k;
for (int i = 1; i <= n; i++)
cout << permutation[i] << " ";
}
int main() {
int n = 5, k = 2;
cout << "The permutation is: ";
findPermutation(n, k);
} Đầu ra
The permutation is: 3 1 2 4 5