ทฤษฎีบท Extended Midy ใน C++

ทฤษฎีบท Midy และ Extended Midy

Midy's Theorem: สำหรับเศษส่วน n/p (p เป็นเฉพาะ) ถ้าทศนิยมซ้ำมีความยาวเป็นเลขคู่ ผลรวมของครึ่งแรกและครึ่งหลัง = 999...9

Extended Midy's Theorem: แบ่งส่วนที่ซ้ำเป็นกลุ่มทุก m หลัก ผลรวมของแต่ละกลุ่มจะหารด้วย 10^m - 1 ลงตัว

ตัวอย่าง

1/17 = 0.0588235294117647... (ซ้ำ 16 หลัก)

แบ่งเป็นกลุ่ม 4 หลัก (m=4): 0588, 2352, 9411, 7647

ผลรวม = 0588+2352+9411+7647 = 19998

10^4 - 1 = 9999, 19998 / 9999 = 2 (ลงตัว) -> Theorem holds!

โปรแกรมตัวอย่าง

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

string findDecimalValue(int num, int den) {
    string res; unordered_map<int, int> mp;
    int rem = num % den;
    while (rem != 0 && mp.find(rem) == mp.end()) {
        mp[rem] = res.length();
        rem *= 10; int part = rem / den; res += to_string(part); rem %= den;
    }
    return (rem == 0) ? "-1" : res.substr(mp[rem]);
}

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

void ExtendedMidysAlgo(string str, int n, int m) {
    if (!isPrime(n)) { cout << "Denominator not prime"; return; }
    int l = str.length();
    if (l%2==0 && l%m==0) {
        vector<int> part(m, 0); int sum = 0;
        for (int i = 0; i < l; i++) part[i/m] = part[i/m]*10 + (str[i]-'0');
        for (int i = 0; i < m; i++) { sum += part[i]; cout << part[i] << " "; }
        cout << endl;
        int res = pow(10, m) - 1;
        if (sum % res == 0) cout << "Extended Midy's theorem holds!";
        else cout << "Extended Midy's theorem doesn't hold!";
    } else if (l%2!=0) cout << "Repeating decimal odd length";
    else cout << "Cannot divide into m digits";
}

int main() {
    int numr = 1, denr = 17, m = 4;
    string res = findDecimalValue(numr, denr);
    if (res == "-1") cout << "No repeating decimal";
    else { cout << "Repeating decimal = " << res << endl; ExtendedMidysAlgo(res, denr, m); }
    return 0;
}

ผลลัพธ์

Repeating decimal = 0588235294117647
588 2352 9411 7647
Extended Midy's theorem holds!