UVA202 - Repeating Decimals（循环小数循环节）

The decimal expansionof the fraction 1/33 is 0.03, where the 03 is used to indicatethat the cycle 03 repeats indefinitely with no intervening digits. In fact, the decimalexpansion of every rationalnumber (fraction) has a repeating cycle as opposedto decimal expansions of irrational numbers, which have no such repeating cycles.

Examples of decimalexpansions of rationalnumbers and theirrepeating cycles are shown below.

Here, we use parentheses to enclose the repeating cycle rather than place a bar over the cycle.

 

fraction 1/6	decimal expansion 0.1(6)	repeating cycle 6	cycle length 1
5/7	0.(714285)	714285	6
1/250	0.004(0)	0	1
300/31	9.(677419354838709)	677419354838709	15
655/990	0.6(61)	61	2

Write a programthat reads numerators and denominators of fractions and determines theirrepeating cycles.

For the purposesof this problem,define a repeating cycle of a fraction to be the firstminimal length string of digits to the right of the decimal that repeats indefinitely with no intervening digits.Thus for example,the repeating cycleof the fraction 1/250 is 0, which begins at position 4 (as opposedto 0 which begins at positions1 or 2 and as opposed to 00 which begins at positions 1 or 4).

 

Input

Each line of the input file consists of an integer numerator, which is nonnegative, followed by an integer denominator, which is positive. None of the input integers exceeds3000. End-of-file indicates the end of input.

 

Output

For each line of input, print the fraction, its decimal expansion through the firstoccurrence of the cycle to the right of the decimal or 50 decimal places (whichever comes first), and the length of the entire repeating cycle.

In writingthe decimal expansion, enclose the repeatingcycle in parentheses when possible. If the entire repeating cycle does not occur within the first50 places, place a left parenthesis where the cycle begins — it will begin within the first 50 places — and place ‘...)’ after the 50th digit.

 

Sample Input

76 25

5 43

1 397

 

Sample Output

76/25  =  3.04(0)

1 = number of digitsin repeating cycle

 

5/43 = 0.(116279069767441860465)

21 = numberof digits in repeating cycle

 

1/397 = 0.(00251889168765743073047858942065491183879093198992...)

99 = numberof digits in repeating cycle

题意：

3000以内的两个数字相除，输出小数结果，若为循环小数，使用（括起最短循环节）

思路：

当存在余数相同的位置时，既是有循环节。

AC CODE：

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define HardBoy main()
#define ForMyLove return 0;
using namespace std;
const int MYDD = 1103+1e4;

int HardBoy {
	int quotient[MYDD];
	int remainder[MYDD];
	int u[MYDD];
	int n, m, t;
	
	while(scanf("%d %d", &n, &m) != EOF) {
		t = n;/*3000以内*/
		memset(quotient, 0, sizeof(quotient));
		memset(u, 0, sizeof(u));
		int cnt = 0;
		quotient[cnt++] = n/m;
		n %= m;
		while(!u[n] && n) {
			u[n] = cnt;
			remainder[cnt] = n;
			quotient[cnt++] = 10*n/m;
			n = 10*n%m;
		}

		printf("%d/%d = %d.", t, m, quotient[0]);
		for (int i = 1 ; i < cnt && i <= 50 ; i++) {
			if (n && remainder[i] == n) printf("(");
			/*存在循环节->开始存在余数相同的位置*/
			printf("%d",quotient[i]);
		}
		if (!n) printf("(0");
		if (cnt > 50) printf("...");
		printf(")\n");
		printf("   %d = number of digits in repeating cycle\n\n",!n? 1:cnt-u[n]);

	}
	ForMyLove
}