C++ 中扩展的米迪定理
米迪定理是用于对n/p表示的数字进行十进制展开的语句,其中n是任何数字,p是素数,而a/p具有偶数周期的重复小数。
在扩展米迪定理中,重复部分被分成m位,那么它们的和是10m-1的倍数。
说明扩展米迪定理的程序:
示例
#includeusing namespace std; string findDecimalValue(int num, int den) { string res; unordered_map mp; int rem = num % den; while ((rem != 0) && (mp.find(rem) == mp.end())) { mp[rem] = res.length(); rem = rem * 10; int part = rem / den; res += to_string(part); rem = 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 is not prime, thus Extended Midy's theorem is not applicable"; return; } int l = str.length(); int part1 = 0, part2 = 0; if (l % 2 == 0 && l % m == 0) { int part[m] = { 0 }, sum = 0, res = 0; for (int i = 0; i < l; i++) { int var = i / m; part[var] = part[var] * 10 + (str[i] - '0'); } for (int i = 0; i < m; i++) { sum = sum + part[i]; cout << part[i] << " "; } cout << endl; 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 << "The repeating decimal is of odd length thus Extended Midy's theorem is not applicable"; } else if (l % m != 0) { cout<<" The repeating decimal can not be divided into m digits"; } } //驱动程序代码 int main() { int numr = 1, denr = 17, m = 4; string res = findDecimalValue(numr, denr); if (res == "-1") cout << "The fraction does not have 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!