দুটি পূর্ণসংখ্যা N এবং K দেওয়া আছে। ১ থেকে N পর্যন্ত পূর্ণসংখ্যার একটি পারমুটেশন খুঁজে বের করতে হবে যাতে 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।
যদি বর্তমান আকারে পর্যবেক্ষণ করা হয়, তবে gcd(i, i+1) = 1, gcd(1, i) = 1 এবং gcd(i, i) = i। যেকোনো সংখ্যা এবং ১-এর GCD সবসময় ১, তাই K প্রায়শই N - 1 হতে পারে। যে পারমুটেশনে P[i] = i, সেখানে gcd(P[i], i) > 1 হওয়া সূচকগুলোর সংখ্যা হবে N - 1। যদি ১ বাদে কোনো দুটি последователь কনসিকিউটিভ উপাদান বদলানো হয়, তবে সেক্ষিক সূচকগুলো ২ করে কমে যাবে, আর ১-এর সাথে বদলালে ১ করে কমে যাবে।
উদাহরণ
#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); }আউটপুট
Permutation is: 2 1 3 4 5
