C++에서 확장된 Midy의 정리

Midy의 정리는 n/p로 표시되는 숫자의 소수 확장에 사용되는 문입니다. 여기서 n은 임의의 숫자이고 p는 소수이며 a/p는 마침표가 짝수인 반복 소수를 가집니다.

Extended Midy's Theorem에서 반복되는 부분을 m자리로 나누고 그 합은 10m - 1의 배수입니다.

확장 미디의 정리를 설명하는 프로그램:

예시

#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 = 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";
   }
}

// Driver code
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!