ทฤษฎี Midy (Midy's Theorem) ใน C++

ได้รับตัวเศษ a_num และตัวส่วน p_den (ต้องเป็นจำนวนเฉพาะ) ตรวจสอบว่าการหาร a_num / p_den สร้างทศนิยมซ้ำที่พิสูจน์ทฤษฎี Midy ได้หรือไม่

ขั้นตอนพิสูจน์ทฤษฎี Midy

1. รับตัวเศษและตัวส่วน (ตัวส่วนต้องเป็นจำนวนเฉพาะ)
2. หาร ตรวจสอบทศนิยมซ้ำ
3. เก็บตัวเลขทศนิยมจนกว่าจะซ้ำ
4. ถ้าจำนวนหลักเป็นเลขคู่ แบ่งครึ่ง
5. บวกครึ่งหน้ากับครึ่งหลัง ถ้าผลลัพธ์เป็นสตริงของ 9 ทั้งหมด → พิสูจน์ทฤษฎี Midy

ตัวอย่าง

Input: a_num = 1, p_den = 19

Output: Repeating decimals are: 052631578947368421 Proved Midy's theorem

คำอธิบาย: 1/19 = 0.052631578947368421... (ซ้ำ 18 หลัก) แบ่งครึ่ง: 052631578 + 947368421 = 999999999 (สตริง 9) → พิสูจน์ได้

Input: a_num = 49, p_den = 7

Output: No Repeating Decimal

คำอธิบาย: 49/7 = 7 หารลงตัว ไม่มีทศนิยมซ้ำ

อัลกอริทึม

• ฟังก์ชัน check(val) ตรวจสอบจำนวนเฉพาะ
• Midys_theorem(a_num, p_den):
  • ใช้ map เก็บตำแหน่ง remainder
  • วน while remainder ≠ 0 และไม่เจอ remainder ซ้ำ: เก็บตำแหน่ง คูณ 10 หารได้ตัวเลขทศนิยมต่อไป
  • ถ้า remainder = 0 → คืน "-1" (ไม่มีทศนิยมซ้ำ)
  • มิฉะนั้น คืน substring ทศนิยมซ้ำ
• check_Midys(str, val):
  • ถ้า val ไม่ใช่เฉพาะ → Not applicable
  • ถ้าความยาว str คู่ → แบ่งครึ่งบวกกัน ถ้าเป็นสตริง 9 → Proved
  • มิฉะนั้น → Not applicable

ตัวอย่างโค้ด C++

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

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

void check_Midys(string str, int val) {
    int len = str.length();
    int first = 0, last = 0;
    if (!check(val)) {
        cout << "\nNot applicable for Midy's theorem";
    } else if (len % 2 == 0) {
        for (int i = 0; i < len / 2; i++) {
            first = first * 10 + (str[i] - '0');
            last = last * 10 + (str[len / 2 + i] - '0');
        }
        cout << "\nProved Midy's theorem";
    } else {
        cout << "\nNot applicable for Midy's theorem";
    }
}

string Midys_theorem(int a_num, int p_den) {
    string result;
    map<int, int> map_val;
    int reminder = a_num % p_den;
    while (reminder != 0 && map_val.find(reminder) == map_val.end()) {
        map_val[reminder] = result.length();
        reminder *= 10;
        int temp = reminder / p_den;
        result += to_string(temp);
        reminder %= p_den;
    }
    if (reminder == 0) return "-1";
    else return result.substr(map_val[reminder]);
}

int main() {
    int a_num = 1, p_den = 19;
    string result = Midys_theorem(a_num, p_den);
    if (result == "-1") cout << "No Repeating Decimal";
    else { cout << "Repeating decimals are: " << result; check_Midys(result, p_den); }
    return 0;
}

ผลลัพธ์

Repeating decimals are: 052631578947368421
Proved Midy's theorem