gcd(P[i], i) > 1 となるインデックスの個数がちょうど K になる順列を C++ で求める方法

問題の概要

2つの整数 N と K が与えられたとします。このとき、範囲 [1, N] の整数からなる順列 P のうち、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(P[i], i) > 1 となるのはインデックス 2、3、4 の 3 箇所だからです。

解法の考え方

この問題には、次のような重要な性質があります。

• gcd(i, i+1) = 1（連続する整数は互いに素）
• gcd(1, i) = 1（1 と任意の数の最大公約数は常に 1）
• gcd(i, i) = i（同じ数同士の最大公約数はその数自身）

これらの性質から、K の最大値は N − 1 であることが分かります。まず P[i] = i となる恒等順列を考えると、gcd(P[i], i) > 1 を満たすインデックスの個数は N − 1 個になります（i = 1 のときだけ gcd(1, 1) = 1 となるため）。

ここからカウントを調整するには、要素の入れ替え（スワップ）を利用します。

• 1 以外の連続する 2 要素を入れ替える → 該当するインデックスの個数がちょうど 2 減る
• 1 と他の要素を入れ替える → 該当するインデックスの個数がちょうど 1 減る

この仕組みを使えば、目的の K に合わせてカウントを段階的に減らしていくことができます。

C++ での実装例

#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];
    // 恒等順列で初期化（カウントは 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) {
            // 連続する 2 要素を入れ替えてカウントを 2 減らす
            swap(P[i], P[i + 1]);
            count -= 2;
        } else if (count - 1 == k) {
            // 1 と入れ替えてカウントを 1 減らす
            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

コードのポイント

• 不可能なケースの判定： k ≥ n の場合や、N が偶数かつ k = 0 の場合は解が存在しないため -1 を出力します。
• 初期化： 恒等順列 P[i] = i から開始し、この時点でのカウントは N − 1 です。
• カウント調整： 目標の K まで、連続要素のスワップ（−2）と 1 とのスワップ（−1）を組み合わせて調整します。

このアルゴリズムの計算量は O(N) であり、非常に効率的に答えを求められます。