Đếm số lần xoay chuỗi số chia hết cho 8 trong C++

Cho một số lớn. Mục tiêu là đếm số lần xoay vòng của số đó mà kết quả chia hết cho 8.

Thay vì xoay thực tế, ta sử dụng tính chất: một số chia hết cho 8 nếu 3 chữ số cuối của nó chia hết cho 8. Ví dụ số 1800, các lần xoay: 1800, 0180, 0018, 8001. Chỉ 1800 chia hết cho 8.

Ví dụ

Đầu vào: num = 15320
Đầu ra: 1
Giải thích: Các lần xoay: 15320, 01532, 20153, 32015, 53201. Chỉ 15320 chia hết cho 8.

Đầu vào: num = 848484
Đầu ra: 3
Giải thích: Các lần xoay: 848484, 484848, 848484, 484848, 848484, 484848. Tất cả các 484848 đều chia hết cho 8.

Giải thuật

• Chuyển số thành chuỗi str.
• Nếu độ dài = 1: kiểm tra chữ số đó chia hết cho 8.
• Nếu độ dài = 2: kiểm tra cả 2 thứ tự (ab và ba).
• Nếu độ dài >= 3: duyệt qua từng cặp 3 chữ số liên tiếp trong chuỗi (tính cả vòng tròn), chuyển thành số và kiểm tra chia hết cho 8.

Ví dụ triển khai

#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';
        return (digit % 8 == 0) ? 1 : 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++;
        }
        // Xử lý vòng tròn: 2 chữ số cuối + 1 chữ số đầu
        digit = (str[length-1] - '0') * 100 + (str[0] - '0') * 10 + (str[1] - '0');
        if (digit % 8 == 0) count++;
        // 1 chữ số cuối + 2 chữ số đầu
        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;
}

Kết quả

Count of rotations divisible by 8 are: 3