POJ 1930 Dead Fraction

Dead Fraction
Time Limit: 1000MS
 
Memory Limit: 30000K
Total Submissions: 1198
 
Accepted: 354
Description
Mike is frantically scrambling to finish his thesis at the last minute. He needs to assemble all his research notes into vaguely coherent form in the next 3 days. Unfortunately, he notices that he had been extremely sloppy in his calculations. Whenever he needed to perform arithmetic, he just plugged it into a calculator and scribbled down as much of the answer as he felt was relevant. Whenever a repeating fraction was displayed, Mike simply reccorded the first few digits followed by "...". For instance, instead of "1/3"he might have written down "0.3333...". Unfortunately, his results require exact fractions! He doesn't have time to redo every calculation, so he needs you to write a program (and FAST!) to automatically deduce the original fractions. 
To make this tenable, he assumes that the original fraction is always the simplest one that produces the given sequence of digits; by simplest, he means the the one with smallest denominator. Also, he assumes that he did not neglect to write down important digits; no digit from the repeating portion of the decimal expansion was left unrecorded (even if this repeating portion was all zeroes).
Input
There are several test cases. For each test case there is one line of input of the form "0.dddd..."where dddd is a string of 1 to 9 digits, not all zero. A line containing 0 follows the last case.
Output
For each case, output the original fraction.
Sample Input

0.2...
0.20...
0.474612399...
0

Sample Output

2/9
1/5
1186531/2500000

Hint
Note that an exact decimal fraction has two repeating expansions (e.g. 1/5 = 0.2000... = 0.19999...).
Source
Waterloo local 2003.09.27
 
 
/* 이 문제는 무한순환 소수를 제시하고 그에 대응하는 최소 분모의 점수를 구하는 것이다.무한순환 소수를 분수로 전환하는 데는 일정한 규칙과 방법이 있다. (1) 입력 소수를 0으로 가정한다.i1 i2 ... it j1 j2 ... jk, 즉 j1j2...jk는 순환하는 부분이다. 그러면 이 점수는 두 부분으로 나누어 순환하지 않는 부분과 순환하는 부분을 계산할 수 있다.(2) 먼저 순환하지 않는 부분을 보면 이것은 매우 간단하다.즉, i1i2...it/10^t, 즉 불순환 부분의 분자 분모는 각각 upd=i1i2...it; downd = 10 ^ t; (3) 순환 부분을 다시 보면 이 부분은 좀 어렵다.수론에서의 전형적인 방법은 분자 up을 j1j2...jk분모down은:10^(t+k)-10^t(4)이면 마지막으로 얻은 점수는 upd/downd+up/down=(upd*down+downd*up)/(down*up)(5) 계산을 주의할 때 약분이다.또한 제목이 순환 부분의 길이를 명확하게 제시하지 않았기 때문에 스스로 매거한 다음에 모든 분수의 분모가 가장 작은 것을 계산해야 한다.또 주의해야 할 것은 입력에 전체 0이 포함된 상황(출력 0/1)이다. 이것은 너무 징그럽다. 제목이 입력이 전부 0이 아니라고 명확하게 말해서 WA를 몇 번이나 해쳤다. */#include #include #include using namespace std; char input[20]; int spos, epos; __int64 minup, mindown; __int64 gcd(__int64 a, __int64 b) { if(b == 0) return a; else return gcd(b, a % b); }//최대 공약수를 이용하여voidtrim(_int64 &up, _int64 &down) {_int64 gcdval;while ((gcdval = gcd (up, down))!= 1) {up/= gcdval;down/= gcdval;}//전체 0 bool allZero () {for(int i=strlen(input)-4;i>=2;i-)if(input[i]!='0')return false;return true;}intmain() {while(scanf('%s', input) & strcmp(input, "0")! = 0) {//완전하지 않을 때 if(! allZero() {mindown = -1; epos = strlen(input) - 4;/문자열 숫자 위치의 끝 위치 입력 spos = 2;/소수점 뒷면의 시작 위치 _int64 up = 0, down = 0, downd = 0, dupdown;//매거 순환 부분의 시작 위치 for(int=spos;t) <=epos;t++){upd=up=0;intk=spos;while(k < t && input[k] == '0') k++;//비순환 부분의 첫 번째 0이 아닌 위치를 찾습니다 for(;k<=epos;k++) {if(k=t)up=up*10+int(input[k]-'0');//통계 순환 부분의 분자 값}downd=pown(10.0,t-spos);//비순환 부분의 분모값down = pow(10.0,epos-spos+1);//모든 소수 부분의 분모값dupdown = pow(10.0,epos-t+1);//순환 부분의 분모값down=down-down/dupdown;//순환 부분 소수의 최종 분모값 if(up!= 0)trim(up,down);//약분if(upd!= 0)trim(upd,downd);//약분__int64 newup, newdown; newup = up * downd + down * upd; newdown = down * downd; if(newup != 0) trim(newup, newdown);//계산 최종 결과if(mindown==-1|newdown