学步园

• Given a rational number expressed as A/B where A and B are integers, find the position of M^th occurrence of digit D (0-9) after decimal point. For example 3/7 = 0.4285714285... (A=3, B=7), so the 2nd (M=2) 4 (D=4) is the 7th digit after decimal point.

  Limits:

  • 0 < A, B, M < 2 x 10⁸

  • 0 <= D <= 9

  Input:

  The first line of the input gives the number of test cases, N. N test cases follow. Each test case consists of one line containing 4 numbers, A, B, M and D separated by spaces.

  Output:

  Each line contains the position (starting from 1) of the specified digit D. Output “0” if it is impossible to find the digit.

  Sample:

  Input	Outut
  7 3 7 1 1 3 7 2 2 3 7 3 6 5 11 2 3 5 11 3 7 20 193 20 6 200000 19893 50 8	6 8 0 0 0 191 470

题目要求是要找出 A/B 的小数部分第M次出现数字D的位置.

我的思路如下:

1. 先将 A/B 化为真分式, A = A % B;

2. 所有的真分式都可以化为有限小数或者无限循环小数;

3. 模拟除法的过程, 商为 (A * 10) / B, 商即为小数部分, 下一次被除数为 A = (A * 10) % B;

4. 如果除的过程中出现 A == 0, 说明是结果是有限小数, 如果出现新得到的被除数与之前得到的某次被除数相同, 则说明结果为无限循环小数, 无限循环部分可由这两次出现的相同的被除数的位置确定;

5. 保存每次4操作中得到的商, 直到为确定结果为有限小数还是无限循环小数;

6. 根据5操作得到的信息即可算出第M次出现数字D的位置, 为了提高效率, 我还在4操作中进行了检测, 如果在还没有确定结果为有限小数还是无限循环小数之前已经找到了第M个数字D, 则立即返回该位置;

7. 注意D = 0的情况;

C语言实现代码如下:

#include <stdio.h>

#define SIZE 100000
#define MAX_INPUT_SIZE 1000

int getMthDigit(int A, int B, int M, int D);

int main()
{
	int n, A, B, M, D;
	int result[MAX_INPUT_SIZE];
	int i;
	scanf("%d", &n);
	fflush(stdout);
	for (i = 0; i < n; i++) {
		scanf("%d %d %d %d", &A, &B, &M, &D);
		fflush(stdout);
		result[i] = getMthDigit(A, B, M, D);
	}
	for (i = 0; i < n; i++) {
		printf("%d\n", result[i]);
	}
	return 0;
}

int getMthDigit(int A, int B, int M, int D)
{

	A = A % B;	/* 将A/B转换为真分式 */
	int loop[SIZE];
	int div[SIZE];
	int circle_len = 1;
	int loop_len = 0;
	int div_len = 0;
	int circle_flag = 0;
	int circle_first, circle_end;	/* 循环部分起始位和结束位 */
	int i;
	int m = 0;
	int count = 0;
	int index[SIZE];

	circle_first = circle_end = 0;

	div[0] = A;
	++div_len;
	while (1) {
		A = A * 10;		
		
		if (0 == A % B) {	/* 除尽，有限小数 */
			circle_flag = 0;
			if (0 != A) {
				loop[loop_len] = A / B;
				++loop_len;
			}
			break;
		}
		loop[loop_len] = A / B;
		++loop_len;

		/* 如果已找到第M个D，则返回 */
		if (D == A / B) {
			++m;
			if (m == M) {
				return loop_len;
			}
		}

		for (i = 0; i < div_len; i++) {
			if (A % B == div[i]) {		/* 循环小数 */
				circle_flag = 1;
				circle_first = i + 1;
				circle_end = div_len;
				break;
			}
		}
		if (circle_first > 0) {
			break;
		}
		div[div_len] = A % B;
		++div_len;
		A = A % B;
	}

	/* 有限小数 */
	if (0 == circle_flag) {
		for (i = 0; i < loop_len; i++) {
			if (D == loop[i]) {
				--M;
			}
			if (0 == M) {
				return (i + 1);
			}
		}
		if (0 == D) {
			return (loop_len + M);
		} else {
			return 0;
		}
	}

	/* 无限循环小数 */
	for (i = circle_first - 1; i <= circle_end - 1; i++) {
		if (D == loop[i]) {
			index[count] = i - circle_first + 2;
			++count;
		}
	}
	for (i = 0; i < circle_first - 1; i++) {
		if (D == loop[i]) {
			--M;
		}
		if (0 == M) {
			return i + 1;
		}
	}
	if (0 == count) {
		return 0;
	}
	circle_len = circle_end - circle_first + 1;
	if ((M % count) != 0) {
		return (circle_first - 1 + M / count * circle_len + index[M%count-1]);
	} else {
		return (circle_first - 1 + (M / count - 1) * circle_len + index[count-1]);
	}
}

gcc下编译通过, 欢迎提出改进意见, 谢谢!