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

Cho hai số nguyên N và K. Cần tìm một hoán vị của các số từ 1 đến N sao cho số lượng chỉ mục (tính từ 1) thỏa mãn gcd(P[i], i) > 1 chính xác bằng K. Ví dụ: N = 4, K = 3, kết quả là [1, 2, 3, 4] vì gcd(1,1)=1, gcd(2,2)=2, gcd(3,3)=3, gcd(4,4)=4.

Quan sát thấy: 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ới 1 luôn là 1, nên K tối đa gần bằng N-1. Xét hoán vị đồng nhất P[i] = i, số chỉ mục thỏa gcd > 1 là N-1. Nếu hoán đổi hai phần tử liên tiếp (trừ 1) sẽ giảm số lượng này đúng 2, hoán đổi với 1 sẽ giảm đúng 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);
}

Kết quả

Permutation is: 2 1 3 4 5