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; }