循环小数

计算 1/x后第n位小数的值，其中x为32位非负整数，n为64位非负整数。

 

#include <stdio.h>

#include <stdlib.h>
#include <map>
#include <vector>

using namespace std;

static int doDiv(int dividant, int divisor, long long n)
{
  vector<int> result;
  map<int, int> repeat;
  int pos = 0;
  int loop_start = 0;
  int loop_end = 0;

  while (true) {
    if (repeat.find(dividant) != repeat.end()) {
      loop_start = repeat[dividant];
      loop_end = pos;
      break;
    }
    repeat.insert(make_pair(dividant, pos++));
    result.push_back(dividant / divisor);
    dividant = dividant % divisor;
    dividant *= 10;
  }
  int loop_len = loop_end - loop_start;
  if (n >= (long long) loop_start) {

    /* be ware of the type cast here. Sometimes the compiler might not do this quite well even if this code segment seems to work whatever */
    int offset = (n - loop_start) % loop_len + loop_start;
    return result[offset];
  } else {
    return result[n];
  }
  
}

int div(int x, long long n)
{
  if (x <= 0) return -1;
  return doDiv(1, x, n);
}

int main()
{
  int x;
  long long n;
  scanf("%d%lld", &x, &n);
  printf("%d\n", div(x, n));
  return 0;
}