gcd（p [i]、i）>1であるインデックスの数がC++で正確にKになるような順列を見つけます

2つの整数NとKがあるとします。gcd（P [i]、i）> 1であるインデックスの数（1 –ベースインデックス）となるように、[1からN]の範囲の整数の順列を見つける必要があります。したがって、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であることがわかります。任意の数と1のGCDは常に1であるため、KはほぼN –1になる可能性があります。P[i]=iである順列を考えてみます。 gcd（P [i]、i）> 1であるインデックスの数は、N – 1になります。1を除く2つの連続する要素を交換すると、そのようなインデックスの数は正確に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