Định lý Midy (Midy's Theorem) trong C++

Cho tử số a_num và mẫu số p_den (số nguyên tố). Kiểm tra định lý Midy: phần thập phân lặp của a_num/p_den có độ dài chẵn, chia đôi 2 nửa cộng lại được chuỗi toàn số 9.

Các bước chứng minh

• Chia a_num / p_den, lấy phần thập phân lặp.
• Nếu độ dài chẵn → chia 2 nửa.
• Cộng 2 nửa → nếu ra chuỗi toàn 9 (999...) → chứng minh định lý Midy.

Ví dụ

Đầu vào: a_num = 1, p_den = 19

Đầu ra: Phần lặp: 052631578947368421 → Chứng minh Midy.

Giải thích: 1/19 = 0.(052631578947368421). Chia đôi: 052631578 + 947368421 = 999999999.

Đầu vào: a_num = 49, p_den = 7

Đầu ra: No Repeating Decimal (49/7=7 hết).

Phương pháp

• Kiểm tra p_den là số nguyên tố.
• Mô phỏng chia lấy dư: lưu vị trí từng dư trong map. Khi dư lặp → tìm chu kỳ.
• Nếu dư = 0 → không lặp.
• Nếu chu kỳ chẵn và mẫu số nguyên tố → chia 2 nửa, cộng, kiểm tra toàn 9.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int val) {
    for (int i=2; i<=val/2; i++) if (val%i==0) return false;
    return true;
}

string Midys_theorem(int a_num, int p_den) {
    string result;
    map<int,int> pos;
    int rem = a_num % p_den;
    while (rem != 0 && pos.find(rem) == pos.end()) {
        pos[rem] = result.length();
        rem *= 10;
        result += to_string(rem / p_den);
        rem %= p_den;
    }
    if (rem == 0) return "-1"; // không lặp
    return result.substr(pos[rem]); // chu kỳ lặp
}

void check_Midys(string str, int val) {
    int len = str.length();
    if (!isPrime(val)) { cout << "\nNot applicable (denominator not prime)"; return; }
    if (len % 2 == 0) {
        long long first=0, last=0;
        for (int i=0; i

Đầu ra chương trình
Repeating decimals are: 052631578947368421
Proved Midy's theorem: 052631578 + 947368421 = 999999999