Cho N, K, tìm hoán vị P của 1..N sao cho đúng K vị trí i thỏa GCD(P[i], i) > 1. Ví dụ N=3, K=1 → 2,1,3.
Giữ K phần tử cuối ở vị trí, các phần tử trước dịch chuyển: phần tử i đặt ở i+1, phần tử N-K đặt ở vị trí 1.
Ví dụ
#include<iostream> using namespace std; void findPermutation(int n, int k) { int permutation[n + 1]; for (int i = 1; i <= n; i++) permutation[i] = i; for (int i = 1; i < n - k; i++) permutation[i + 1] = i; permutation[1] = n - k; for (int i = 1; i <= n; i++) cout << permutation[i] << " "; } int main() { int n = 5, k = 2; cout << "The permutation is: "; findPermutation(n, k); }
Kết quả
The permutation is: 3 1 2 4 5