AOJ : 2049 - Headstrong Student

AOJ ACM-ICPC-OBOG 実装問題

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2049
XとYが入力されます.
X/Yを計算し, 循環小数となるのであれば, 小数点から循環開始の桁までの桁数と, 循環開始から終了までの桁数を答えます.
循環小数とならないのであれば, 小数点以下何桁であるかを出力し, その右に0を出力します(循環部はないという意味で).

アルゴリズム

Period (http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0113&lang=jp) の問題を少し改良するだけで通ります.
昔解いたことがあるコードをそのまま持ってきて解きました.
僕の解法は, 公式講評の解法(1)の方を使って解いていたようです.


http://acm-icpc.aitea.net/index.php?2008%2FPractice%2F%CC%CF%B5%BC%C3%CF%B6%E8%CD%BD%C1%AA%2F%B9%D6%C9%BE

プログラム

#include <stdio.h>
#include <string.h>

int a[1000001];

int main(void){
  int i,j,x,y,p,q,flg;

  while(scanf("%d%d",&x,&y) && (x||y)){
    flg = 0; //1:循環する 0:循環しない
    memset(a,-1,sizeof(a));

    for(i=0;;i++){
      x = x - y * (x / y);
      if(x == 0) break;
      if(a[x] != -1){
        flg = 1;
        j = a[x];
        break;
      }
      a[x] = i;
      x *= 10;
    }

    printf("%d %d\n",flg ? j : i, flg ? i-j : 0);
  }

  return 0;
}