หา Permutation ที่มีดัชนี i ทำให้ gcd(p[i], i) > 1 จำนวน K ตัวใน C++

โจทย์

ให้ N และ K ต้องการหา Permutation ของ 1..N ที่มีดัชนี i (1-based) ทำให้ gcd(P[i], i) > 1 จำนวนพอดี K ตัว

ตัวอย่าง: N=4, K=3 → [1,2,3,4] เพราะ gcd(1,1)=1, gcd(2,2)=2, gcd(3,3)=3, gcd(4,4)=4 → มี 3 ตัว

ข้อสังเกตสำคัญ

• gcd(i, i+1) = 1, gcd(1, i) = 1, gcd(i, i) = i
• Permutation P[i]=i ให้ K = N-1 (สูงสุด)
• Swap ติดกัน (ไม่รวม 1) → ลด K ลง 2
• Swap กับ 1 → ลด K ลง 1

ตัวอย่างโค้ด C++

#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 - 2 > 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);
}

ผลลัพธ์

Permutation is: 2 1 3 4 5