找到一个排列，使得在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