Problem 2049 : Headstrong Student

Problem B: Headstrong Student
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2049

• 問題概要

整数が二つ与えられて、それらの割り算の結果が循環するかどうか。
循環するなら長さを。循環を始めるポイントを出力しなさい。

• 解法

tmp = x mod y
x = tmp * 10
を繰り返す。
tmpはあまりです。
同じあまりが二回でてきたら循環している。
あまりが０になった割り切れてる。
なんかい繰り返したときにそのあまりがでてきたか記憶して、次でてきたときとの
ループ回数の差が循環の長さである。

mapでそれらを記憶すると遅くなるので、思い切って配列をガボッととってしまいましょう。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;


main(){
  int x, y;
  while(cin >> x >> y){
    if(x + y == 0)break;
    int index[1000000];
    rep(i, 1000000)index[i] = -1;
    int cnt = 0;
    while(1){
      int tmp = x % y;
      if(tmp == 0){
	cout << cnt << ' ' << 0 << endl;
	break;
      }
      else if(index[tmp] == -1)index[tmp] = cnt;
      else{
	cout << index[tmp]  << ' ' << cnt - index[tmp] << endl;
	break;
      }
      cnt++;
      x = tmp * 10;
    }
  }
}