UVa 202 : Repeating Decimals

問題リンク : http://uva.onlinejudge.org/external/2/202.html

問題概要 :
2つの整数 numerator, denominator があたえられる
numerator / denominator の結果とその小数点以下に含まれる最小のサイクルを見つけ、指定された形式で出力せよ

解法：
Cycle detection - Wikipedia, the free encyclopedia
上にあるFloyd's Cycle-Finding Algorithmを利用した
詳しくは上のサイト参考
もしくは日本語のwikipediaを読むと良いかも(そこに載っている図を見ると良い)

コード :

#include<iostream>
#include<cmath>
#include<cstdio>
#include<climits>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)

using namespace std;

typedef pair<int,int> ii;

int numerator,denominator;
string ans;

int f(int x)
{
  x = x * 10;
  return x % denominator;
}

ii floydCycleFinding(int x0)
{
  int tortoise = f(x0), hare = f(f(x0));
  while(tortoise != hare)
    {
      tortoise = f(tortoise);
      hare = f(f(hare));
    }
  hare = x0;
  int mu,lambda;
  mu = 0, lambda = 1;
  while(tortoise != hare)
    {
      tortoise = f(tortoise);
      hare = f(hare);
      mu++;
    }

  hare = f(tortoise);
  while(tortoise != hare)
    {
      hare = f(hare);
      lambda++;
    }
  return ii(mu,lambda);
}

void print(int num,int limit,int sp,int cur)
{
  num = num * 10;
  if(sp == cur)
    {
      cout << "(";
      if(sp == limit)
	{
	  cout << 0;
	}
    }
  if(cur >= 50)
    {
      cout << "...)\n";
      return;
    }
  if(cur >= limit)
    {
      cout << ")\n";
      return;
    }
  cout << (int)(num/denominator);
  print(num%denominator,limit,sp,cur+1);
}

int main()
{
  while(scanf("%d %d",&numerator,&denominator) != EOF)
    {
      ans.clear();
      ii res = floydCycleFinding(numerator%denominator);

      cout << numerator << "/" << denominator << " = " << (int)(numerator/denominator) << ".";
      print(numerator%denominator,res.first+res.second,res.first,0);
      cout << "   " << res.second << " = number of digits in repeating cycle\n\n";
    }
  return 0;
}