在 C++ 中寻找一个排列，使得 gcd(p[i], i) > 1 的索引个数恰好为 K

假设我们有两个整数 N 和 K。我们必须找到一个来自范围 [1 到 N] 的整数排列，使得 gcd(P[i], i) > 1 的索引（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。由于任何数与 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

更新于：2019年12月18日

浏览量：180

开启你的职业生涯

完成课程获得认证

开始学习
广告