C++で8で割り切れる回転の個数を数える方法

大きな整数が与えられます。目的は、その数 num を回転（ローテーション）させた結果のうち、8で割り切れるものの個数を数えることです。

回転を何度も繰り返して毎回割り算を実行するのは非効率です。そこで、8の倍数に関する性質を利用します。整数の下3桁が8で割り切れるならば、その数全体も8で割り切れるという性質です。例えば 1800 の場合、回転は 1800、0180、0018、8001 となり、このうち 8 で割り切れるのは 1800 のみです。

具体例で確認してみましょう。

入力 − num = 15320

出力 − 8で割り切れる回転数： 1

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

15320, 01532, 20153, 32015, 53201
このうち、8で割り切れるのは 15320 のみです。

入力 − num = 848484

出力 − 8で割り切れる回転数： 3

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

848484, 484848, 848484, 484848, 848484, 484848
このうち、484848 はすべて8で割り切れます。

プログラムで使用するアプローチ

数値を文字列に変換し、forループで各桁を走査します。連続する3桁ずつを整数に変換し、8で割り切れるかどうかを判定します。割り切れた場合はカウントを1つ増やします。

• 数値を long long 型の num として受け取ります。

• 関数 Rotation_8(long long num) は、num を引数に取り、8で割り切れる回転の個数を返します。

• num を文字列に変換します（str = to_string(num)）。

• num の桁数を length = str.length() として取得します。

• 3桁分の整数値を一時的に保持するための変数 digit を用意します。

• カウント用変数 count を 0 で初期化します。

• length が 1 の場合（1桁のみ）： その1桁を整数に変換し（digit = str.at(0) - '0'）、8で割り切れるかを判定して 1 または 0 を返します。

• length が 2 の場合（2桁のみ）： 元の並びと入れ替えた並びの両方を整数として作成し（part_1、part_2）、それぞれ8で割り切れるかを判定して結果を返します。

• length が 3 以上の場合： forループで i = 0 から i = length-3 まで文字列を走査し、連続する3文字を digit = (str[i] - '0') * 100 + (str[i + 1] - '0') * 10 + (str[i + 2] - '0'); として整数値に変換します。digit が8で割り切れる場合は count をインクリメントします。

• 同様に、末尾1桁と先頭2桁で構成される組み合わせについても digit = (str[length - 1] - '0') * 100 + (str[0] - '0') * 10 + (str[1] - '0'); として判定します。

• さらに、末尾2桁と先頭1桁で構成される組み合わせについても同じ処理を行い、count を更新します。

• 最後に count を結果として返します。

サンプルコード

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

出力

上記のコードを実行すると、次の出力が生成されます −

Count of rotations divisible by 8 are: 3