Pの競プロ記

競技プログラミングに関することを書きます。

AOJ 2049 Headstrong Student

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2049

循環小数に関する問題です。
x / y の割り算(x < y)をして、小数第一位から循環が始まるまでの桁数と循環のひとサイクル分の長さを求めます。


解法


筆算で計算するのと同じようなことをループを回しながらやればよいです。
ここで重要となる考え方があり、それを「鳩ノ巣原理」といいます。(呼び名は後から知りました)

http://ja.wikipedia.org/wiki/%E9%B3%A9%E3%81%AE%E5%B7%A3%E5%8E%9F%E7%90%86

上のサイトを読めば大体何を言っているか分かると思いますが、要するに x / y の計算をするときに筆算のようなことをy+1回やれば必ず同じ余りが1回は出てくるということになります。

あとはある余りが何回目の割り算で出てきたかを保存しておけばよいです。

ちなみに「AOJ 0113 Period」という問題がとてもこの問題と似ているので参考にしてみてはどうでしょうか。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0113


ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cassert>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i, 0, n)
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
typedef pair<int,int> P;
typedef long long ll;
 
static const int INF = (1<<29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
 
int number[1000000];
 
void solve(int x, int y){
  int a,b;
  memset(number,-1,sizeof(number));
  for(int i = 0 ; ; i++){
    if(number[x] != -1){
      if(x==0){
        a = i-1;
        b = 0;
      }
      else{
        a = number[x];
        b = i - number[x];
      }
      break;
    }
    number[x] = i;
    x *= 10;
    x %= y;
  }
  cout << a << " " << b << endl;
}
 
int main(){
  int x,y;
  while(cin >> x >> y, (x|y)){
    solve(x,y);
  }
  return 0;
}