C++에서 gcd(p[i], i)> 1인 인덱스 수가 정확히 K인 순열 찾기

두 개의 정수 N과 K가 있다고 가정합니다. gcd(P[i], i)> 1인 인덱스의 수(1 – 기본 인덱싱)가 되도록 [1에서 N] 범위의 정수 순열을 찾아야 합니다. 정확히 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임을 알 수 있습니다. 임의의 수와 1의 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