UVa 202 循环小数 题解

2022-03-20

题目要求输入整数 $a\geq0$ 和整数 $b\geq1$ ,输出分数 $\frac{a}{b}$ 的循环小数表示与循环节长度。

这题的难点在于判断循环节开始的位置,对于纯循环小数来说,只要判断当前余数是否等于第一次进入循环的被除数,但对于混循环小数就没那么简单了。

例如对于$\frac{5}{1750} = 0.00\overline{285714}$循环从第二位小数之后开始。 事实上这题可以用数组记录每次计算的被除数,然后判断当前计算的余数是否在数组中,不过这并不是最优解。

考虑一个一般的情况,混循环小数 $\frac{a}{b}=0.\underbrace{a_0…a_0}_{n个}\overline{a_1…a_m}$ 循环从第$n$位之后开始,循环节长度为$m$。

显然,由 $\frac{10^na}{b}=0.\overline{a_1…a_m}$ 可以将混循环小数化为纯循环小数。 考虑可以除尽的情况,所以对于十进制来说,循环节开始的位置$n$由分母比分子多出的10、5、2的因数个数决定。这个结论也可以推广到其他进制。

故对于开头的例子有 $\frac{5}{1750}=\frac{1}{10×5×7}$ ,分母有因子 $10, 5$ ,则循环从第二位之后开始。 代码如下,

/* 习题3-8 循环小数(Repeating Decimals, ACM/ICPC World Finals 1990, UVa202)
 */
#include <stdio.h>
// greatest common divisor
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
// factor counter 10, 5, 2
int fc(int a) {
  if (!a)
    return 0;
  int a10, a5, a2;
  for (a10 = 0; !(a % 10); a /= 10)
    a10++;
  for (a5 = 0; !(a % 5); a /= 5)
    a5++;
  for (a2 = 0; !(a % 2); a /= 2)
    a2++;
  return a10 + a5 + a2;
}
int main() {
  int a, b, ab;
  while (scanf("%d%d", &a, &b) == 2) {
    ab = gcd(a, b);
    printf("%d/%d = %d.", a, b, a / b);
    a = a / ab;
    b = b / ab;
    a %= b;
    int m = 0, n = fc(b); // 循环节长度 开始循环位数
    int first_a = 0;
    while (first_a != a) {
      if (m == n) {
        putchar('(');
        first_a = a;
      }
      if (m < 50)
        putchar('0' + 10 * a / b);
      else if (m == 50)
        printf("...");
      if ((a = 10 * a % b) == 0) {
        m = 0;
        break;
      }
      m++;
    }
    if (m)
      printf(")\n   %d = number of digits in repeating cycle\n\n", m - n);
    else
      printf("(0)\n   %d = number of digits in repeating cycle\n\n", 1);
  }
  return 0;
}

7-2 一元多项式的乘法与加法运算 题解