एक क्रमचय खोजें जैसे कि सूचकांकों की संख्या जिसके लिए gcd(p[i], i)> 1 C++ में बिल्कुल K है

मान लीजिए कि हमारे पास दो पूर्णांक N और K हैं। हमें [1 से N] तक के पूर्णांकों का क्रमचय इस प्रकार ज्ञात करना है कि सूचकांकों की संख्या (1 - आधार अनुक्रमण) जहां 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, जीसीडी(4, 4) =4

अगर हम इसे ध्यान से देखें, तो हम पा सकते हैं कि gcd(i, i+1) =1, gcd(1, i) =1 और gcd(i, i) =i। चूँकि किसी भी संख्या का GCD और 1 हमेशा 1 होता है, K लगभग N - 1 हो सकता है। क्रमपरिवर्तन पर विचार करें जहाँ P[i] =i। सूचकांकों की संख्या जहां gcd(P[i], i)> 1, N-1 होगा। यदि हम 1 को छोड़कर लगातार दो तत्वों की अदला-बदली करते हैं, तो ऐसे सूचकांकों की संख्या ठीक 2 से कम हो जाएगी, और 1 के साथ अदला-बदली करने से गिनती कम हो जाएगी। ठीक 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