找到一个排列，使得在C ++中gcd（p [i]，i）> 1的索引数恰好是K

假设我们有两个整数N和K。我们必须找到一个从[1到N]范围内的整数的排列，以使索引数（1 –基本索引）其中gcd（P [i]，i）> 1为因此，如果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始终为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