数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在 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
广告