Posted on 2009-05-16 12:08
superman 閱讀(300)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 int gcd(const int a, const int b)
6 {
7 if (b == 0)
8 return a;
9 return gcd(b, a % b);
10 }
11
12 class Faction
13 {
14 private:
15 int fz, fm;
16
17 public:
18 void to_proper_faction()
19 {
20 int t;
21 while ((t = gcd(fz, fm)) != 1)
22 fz /= t, fm /= t;
23 }
24
25 Faction() { fz = 1, fm = 0; }
26 Faction(const int n) { fz = n, fm = 1; }
27 Faction(const int a, const int b) { fz = a, fm = b; to_proper_faction(); }
28
29 int getfz() { return fz; }
30
31 bool isInteger() { return fm == 1; }
32 bool isNegative() { return fz < 0 || fm < 0; }
33
34 //======================================================
35 Faction operator + (const Faction &b)
36 {
37 int t = fm * b.fm;
38 Faction c(t / fm * fz + t / b.fm * b.fz, t);
39 return c;
40 }
41 Faction operator - (const Faction &b)
42 {
43 int t = fm * b.fm;
44 Faction c(t / fm * fz - t / b.fm * b.fz, t);
45 return c;
46 }
47 Faction operator * (const Faction &b)
48 {
49 Faction c(fz * b.fz, fm * b.fm);
50 return c;
51 }
52 Faction operator / (const Faction &b)
53 {
54 Faction c(fz * b.fm, fm * b.fz);
55 return c;
56 }
57 //======================================================
58 Faction operator + (const int n) { return *this + Faction(n); }
59 Faction operator - (const int n) { return *this - Faction(n); }
60 Faction operator * (const int n) { return *this * Faction(n); }
61 Faction operator / (const int n) { return *this / Faction(n); }
62
63 //======================================================
64 void operator += (const Faction &b) { *this = *this + b; }
65 void operator -= (const Faction &b) { *this = *this - b; }
66 void operator *= (const Faction &b) { *this = *this * b; }
67 void operator /= (const Faction &b) { *this = *this / b; }
68
69 //======================================================
70 friend std::istream& operator >> (std::istream &is, Faction &b)
71 {
72 is >> b.fz >> b.fm;
73 return is;
74 }
75 friend std::ostream& operator << (std::ostream &os, const Faction &b)
76 {
77 if (b.fm == 1)
78 os << b.fz;
79 else
80 os << b.fz << '/' << b.fm;
81 return os;
82 }
83 } ;
84
85 int main()
86 {
87 freopen("ratios.in", "r", stdin);
88 freopen("ratios.out", "w", stdout);
89
90 int n = 3;
91 Faction o[10][10], a[10][10], b[10], x[10];
92
93 int t;
94 for (int i = 0; i < n; i++)
95 {
96 cin >> t;
97 b[i] = t;
98 }
99 for (int i = 0; i < n; i++)
100 for (int j = 0; j < n; j++)
101 {
102 cin >> t;
103 o[j][i] = t;
104 }
105
106 for (int p = 7; p < 100; p++)
107 {
108 for (int i = 0; i < n; i++)
109 for (int j = 0; j < n; j++)
110 a[i][j] = o[i][j];
111
112 for (int i = 0; i < n; i++)
113 a[i][n] = b[i] * p;
114
115 for (int i = 0; i < n - 1; i++)
116 for (int j = i + 1; j < n; j++)
117 {
118 Faction t = a[j][i] / a[i][i];
119 for (int k = 0; k <= n; k++)
120 a[j][k] -= t * a[i][k];
121 }
122 //====================================
123 x[n - 1] = a[n - 1][n] / a[n - 1][n - 1];
124 for (int i = n - 2; i >= 0; i--)
125 {
126 x[i] = a[i][n];
127 for (int j = i + 1; j < n; j++)
128 x[i] -= a[i][j] * x[j];
129 x[i] /= a[i][i];
130 }
131
132 int i;
133 for (i = 0; i < n; i++)
134 if (x[i].isNegative() || x[i].isInteger() == false)
135 break;
136 if (i == n)
137 {
138 x[n] = p;
139
140 int tx[10], tg;
141 for (int i = 0; i <= n; i++)
142 tx[i] = x[i].getfz();
143 tg = tx[0];
144 for (int i = 1; i <= n; i++)
145 tg = gcd(tg, tx[i]);
146
147 if (tg != 1)
148 for (int i = 0; i <= n; i++)
149 tx[i] /= tg;
150
151 for (int i = 0; i <= n; i++)
152 cout << tx[i] << (i == n ? '\n' : ' ');
153
154 return 0;
155 }
156 }
157
158 cout << "NONE" << endl;
159
160 return 0;
161 }
162