ধরুন আমাদের দুটি পূর্ণসংখ্যা 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 উপাদানগুলিকে তাদের জায়গায় রাখব, বাকি উপাদানগুলি সরানো হবে, যেমন ith উপাদানটিকে (i + 1) তম অবস্থানে রাখা হবে এবং (N - K)তম উপাদানটি রাখা হবে অবস্থান 1, কারণ 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
