【C++】ASCII値がkと互いに素な小文字だけを大文字に変換する方法

このチュートリアルでは、与えられた文字列のうち、ASCII値が整数kと互いに素（coprime）である小文字のみを大文字に変換するC++プログラムについて解説します。

問題の概要

入力として、1つの文字列と1つの整数値kが与えられます。私たちのタスクは、文字列を先頭から順に走査し、各文字のASCII値がkと互いに素である場合に、その小文字を対応する大文字へ変換することです。それ以外の文字はそのまま維持します。

互いに素であるかどうかの判定には、最大公約数（GCD）を利用します。ASCII値とkのGCDが1であれば、両者は互いに素であると判断できます。

アルゴリズムのポイント

• 各文字をint型にキャストしてASCII値を取得する
• その文字が小文字（'a'〜'z'の範囲）であるかを確認する
• C++標準ライブラリの __gcd() 関数を使って、ASCII値とkの最大公約数を求める
• GCDが1の場合のみ、文字コードから32を引いて大文字に変換する

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 与えられた文字列を変換する関数
void convert_string(string s, int k){
    int l = s.length();
    for (int i = 0; i < l; i++) {
        int ascii = (int)s[i];
        // ASCII値がkと互いに素かどうかを判定
        if (ascii >= 'a' && ascii <= 'z' && __gcd(ascii, k) == 1) {
            char c = s[i] - 32;
            s[i] = c;
        }
    }
    cout << s << "\n";
}
int main(){
    string s = "tutorialspoint";
    int k = 3;
    convert_string(s, k);
    return 0;
}

実行結果

TuToriAlSPoiNT

解説

この例では、文字列「tutorialspoint」と整数k=3を渡しています。各小文字のASCII値と3のGCDを計算し、結果が1となる文字だけが大文字に変換されます。

例えば、't' のASCII値は116で、116と3のGCDは1なので大文字の'T'に変換されます。一方、'o' のASCII値は111で、111と3のGCDは3となるため、元の小文字のまま保持されます。

このように、GCDによる互いに素の判定とASCIIコードの操作を組み合わせることで、条件を満たす文字だけを選択的に変換できます。計算量は文字列の長さをnとするとO(n log k)程度で、非常に効率的な処理です。