Extended Midy 's theorem | C ++ program to demonstrate extended Midy 's theorem ; Returns repeating sequence of a fraction . If repeating sequence doesn 't exits, then returns -1 ; Create a map to store already seen remainders remainder is used as key and its position in result is stored as value . Note that we need position for cases like 1 / 6. In this case , the recurring sequence doesn 't start from first  remainder.  ; Find first remainder ; Keep finding remainder until either remainder becomes 0 or repeats ; Store this remainder ; Multiply remainder with 10 ; Append rem / denr to result ; Update remainder ; Checks whether a number is prime or not ; If all conditions are met , it proves Extended Midy 's theorem ; Dividing repeated part into m parts ; Computing sum of parts . ; Checking for Extended Midy ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string fractionToDecimal ( int numerator , int denominator ) { string res ; unordered_map < int , int > mp ; int rem = numerator % denominator ; while ( ( rem != 0 ) && ( mp . find ( rem ) == mp . end ( ) ) ) { mp [ rem ] = res . length ( ) ; rem = rem * 10 ; int res_part = rem / denominator ; res += to_string ( res_part ) ; rem = rem % denominator ; } 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 ExtendedMidys ( 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 = fractionToDecimal ( numr , denr ) ; if ( res == " - 1" ) cout << " The ▁ fraction ▁ does ▁ not " << " ▁ have ▁ repeating ▁ decimal " ; else { cout << " Repeating ▁ decimal ▁ = ▁ " << res << endl ; ExtendedMidys ( res , denr , m ) ; } return 0 ; }