মনে করুন আমাদের দুটি পূর্ণসংখ্যা N এবং K আছে, এবং আমাদের প্রথম Nটি প্রাকৃতিক সংখ্যার পারমিউটেশন P বের করতে হবে যাতে ঠিক Kটি উপাদান থাকে যা শর্ত GCD(P[i], i) > 1 পূরণ করে সব 1 <= i <= N-এর জন্য। তাই যখন N = 3 এবং K = 1, তবে আউটপুট হবে 2, 1, 3। এবং gcd(2, 1) = 1, gcd(1, 2) = 1, gcd(3, 3) = 3
অ্যাপ্রোচটি সহজ। আমরা শেষের kটি উপাদানকে তাদের জায়গায় রেখে দেব, বাকি উপাদানগুলো সরিয়ে দেব, যেন i-তম উপাদান (i+1)তম পজিশনে যায় এবং (N-K)তম উপাদান ১ নম্বর পজিশনে থাকে, কারণ gcd(x, x+1) = 1।
উদাহরণ
#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);
}
আউটপুট
The permutation is: 3 1 2 4 5
