C++で4で割り切れる回転の個数を効率的に数える方法

はじめに

この記事では、大きな整数が与えられたとき、その回転（ローテーション）の中で4で割り切れるものがいくつあるかを数える方法を解説します。

回転操作を実際に何度も繰り返して数値を組み立てるのは非効率です。そこで、4の倍数に関する重要な性質を利用します。それは「整数の下2桁が4で割り切れるならば、その整数全体も4で割り切れる」という性質です。

例えば、1234の回転は1234、4123、3412、2341の4通りありますが、このうち3412は下2桁が「12」であり、12は4で割り切れるため、3412全体も4で割り切れます。

入出力例

入力 − num = 15324

出力 − 4で割り切れる回転の個数: 2

説明 − 回転は以下の5通りです。

15324, 41532, 24153, 32415, 53241

このうち、15324（下2桁が24）と41532（下2桁が32）が4で割り切れます。

入力 − num = 848484

出力 − 4で割り切れる回転の個数: 6

説明 − 回転は以下の6通りです。

848484, 484848, 848484, 484848, 848484, 484848

すべての回転が4で割り切れます。

アルゴリズムの考え方

数値を文字列に変換し、forループで各桁を走査します。隣接する2桁ずつを取り出して整数に変換し、4で割り切れるかを判定します。割り切れた場合はカウントを1増やします。さらに、末尾の桁と先頭の桁からなるペアも、回転によって下2桁になり得るため同様に判定します。

• 数値をlong long型のnumとして受け取ります。
• 関数Rotation_4(long long num)は、numの回転のうち4で割り切れるものの個数を返します。
• to_string()を使ってnumを文字列strに変換します。
• 桁数lengthはstr.length()で求めます。
• 一時変数digitを用意し、2桁ペアの整数値を格納します。
• カウントcountを0で初期化します。
• lengthが1の場合（1桁のみ）は、digit=(str.at(0)-'0')で整数化し、4で割り切れれば1、そうでなければ0を返します。
• i=0からi<length-1までforループで走査し、digit=(str.at(i)-'0')*10+(str.at(i+1)-'0')として2桁の数を作ります。各ペアは回転後の下2桁に相当するためです。
• digitが4で割り切れる場合はcountをインクリメントします。
• 末尾の桁と先頭の桁のペアについても、digit=(str.at(length-1)-'0')*10+(str.at(0)-'0')として同様に判定し、countを更新します。
• 最後にcountを結果として返します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int Rotation_4(long long num){
    string str = to_string(num);
    int length = str.length();
    int digit = 0, count = 0;
    if (length == 1){
        digit=(str.at(0)-'0');
        if(digit%4 == 0){
            return 1;
        }
        else{
            return 0;
        }
    }
    for (int i=0; i<(length-1); i++){
        digit = (str.at(i)-'0')*10 + (str.at(i+1)-'0');
        if(digit%4 == 0){
            count++;
        }
    }
    digit = (str.at(length-1)-'0')*10 + (str.at(0)-'0');
    if(digit%4 == 0){
        count++;
    }
    return count;
}
int main(){
    long long num = 24040;
    cout<<"Count of rotations divisible by 4 are: "<<Rotation_4(num);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Count of rotations divisible by 4 are: 4