AOJ 2049 - Headstrong Student

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2049

概要

2つの正の整数 x, y が与えられるので，x を y で割った値を小数で表現したとき，循環節が始まる桁と循環節の長さを答える．

制約

• 1 <= x < y < 10^6

解法

筆算の要領で調べるだけ．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int gcd(int a, int b)
 6 {
 7   if (a < b) {
 8     swap(a, b);
 9   }
10   for (int r; (r = a % b) != 0;) {
11     a = b;
12     b = r;
13   }
14   return b;
15 }
16 
17 int main()
18 {
19   int x, y;
20   while (cin >> x >> y && x != 0) {
21     const int g = gcd(x, y);
22     x /= g; y /= g;
23     vector<int> seen(y, -1);
24     seen[x] = 0;
25     for (int c = 1;; c++) {
26       x = (10*x) % y;
27       if (x == 0) {
28         cout << c << " 0" << endl;
29         break;
30       } else if (seen[x] != -1) {
31         cout << seen[x] << ' ' << c-seen[x] << endl;
32         break;
33       }
34       seen[x] = c;
35     }
36   }
37   return 0;
38 }