fork download
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cassert>
  4. #include <iostream>
  5. #include <set>
  6. #include <vector>
  7. #include <cstring>
  8. #include <string>
  9. #include <algorithm>
  10. #include <numeric>
  11. #include <cmath>
  12. #include <complex>
  13. #include <map>
  14. #include <queue>
  15. using namespace std;
  16. typedef long long ll;
  17. typedef vector<int> vi;
  18. typedef vector<ll> vl;
  19. typedef vector<vi> vvi;
  20. typedef vector<vl> vvl;
  21. typedef vector<double> vd;
  22. typedef pair<int, int> pii;
  23. typedef pair<double, double> pdd;
  24. typedef vector<pii> vii;
  25. typedef vector<string> vs;
  26.  
  27. void out(vl v) {
  28. for (int i = 0; i < v.size(); ++i)
  29. cout << v[i] << ' ';
  30. cout << endl;
  31. }
  32.  
  33. void out(vvl v) {
  34. for (int i = 0; i < v.size(); ++i)
  35. out(v[i]);
  36. cout << endl;
  37. }
  38.  
  39. void outerr(vl v) {
  40. for (int i = 0; i < v.size(); ++i)
  41. cerr << v[i] << ' ';
  42. cerr << endl;
  43. }
  44.  
  45. void outerr(vvl v) {
  46. for (int i = 0; i < v.size(); ++i)
  47. outerr(v[i]);
  48. cerr << endl;
  49. }
  50.  
  51. vvl id (int n) {
  52. vvl v(n, vl(n));
  53. for (int i =0 ; i < n; ++i) v[i][i] = 1;
  54. return v;
  55. }
  56.  
  57. void model(vvl & v, vl x, int inv) {
  58. if (x.size() == 2) {
  59. if (x[1] == -1) {
  60. for (int j = 0; j < v.size(); ++j)
  61. v[x[0]][j] *= -1;
  62. return;
  63. }
  64. model(v, {x[0], x[1], 1}, 0);
  65. model(v, {x[1], x[0], -1}, 0);
  66. model(v, {x[0], x[1], 1}, 0);
  67. model(v, {x[0], -1}, 0);
  68. return;
  69. }
  70. if (inv) {
  71. x[2] *= -1;
  72. }
  73. for (int j = 0; j < v.size(); ++j)
  74. v[x[1]][j] += v[x[0]][j]*x[2];
  75. }
  76.  
  77. vvl tr(vvl v) {
  78. int n = v.size();
  79. for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) {
  80. swap(v[i][j], v[j][i]);
  81. }
  82. return v;
  83. }
  84.  
  85. vvl mul(vvl x, vvl y) {
  86. int n = x.size();
  87. vvl res(n, vl(n));
  88. for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
  89. for (int l = 0; l < n; ++l) {
  90. //if (abs(y[l][j])) assert(abs(x[i][l]) < 4e18/abs(y[l][j]));
  91. res[i][j] += x[i][l]*y[l][j];
  92. //assert(abs(res[i][j]) < 4e18);
  93. }
  94. }
  95. return res;
  96. }
  97.  
  98. int main() {
  99. freopen("higher.in", "r", stdin);
  100. freopen("higher.out", "w", stdout);
  101. int n = 4;
  102. for (int mask = 0; mask < 100000; ++mask) {
  103. int m = mask;
  104. }while (cin >> n) {
  105. if (n == 0) break;
  106. vvl a(n, vl(n));
  107. for (int i = 0; i < n; ++i) for (int j =0 ; j < n; ++j) {
  108. //a[i][j] = m % 4 - 2;
  109. //m /= 4;
  110. cin >> a[i][j];
  111. }
  112. vvl a0 = a;
  113. int b = 0;
  114. vvl row, col;
  115. while (b < n) {
  116. //outerr (a);
  117. // out (a);
  118. ll mi=2.1e18;
  119. int r,c;
  120. for (int i = b; i < n; ++i) for (int j = b; j < n; ++j) {
  121. if (a[i][j] && abs(a[i][j]) < mi) {
  122. r=i; c=j;
  123. mi = abs(a[i][j]);
  124. }
  125. }
  126. if (mi > 2e18) break;
  127. int r1 = -1, c1 = -1;
  128. ll m1 = mi;
  129. for (int i = b; i < n; ++i) for (int j = b; j < n; ++j) if (abs(a[i][j])) {
  130. for (int i1 = b; i1 < n; ++i1) if (i1 != i && abs(a[i1][j]) % abs(a[i][j])) {
  131. if (abs(a[i1][j]) % abs(a[i][j]) < m1) {
  132. m1 = abs(a[i1][j]) % abs(a[i][j]);
  133. r = i;
  134. r1 = i1;
  135. c = c1 = j;
  136. }
  137. }
  138. for (int j1 = b; j1 < n; ++j1) if (j1 != j && abs(a[i][j1]) % abs(a[i][j])) {
  139. if (abs(a[i][j1]) % abs(a[i][j]) < m1) {
  140. m1 = abs(a[i][j1]) % abs(a[i][j]);
  141. r = r1 = i;
  142. c = j;
  143. c1 = j1;
  144. }
  145. }
  146. }
  147. if (m1 == mi) {
  148. for (int i = b; i < n; ++i) for (int j = b; j < n; ++j) if (abs(a[i][j])) {
  149. for (int i1 = b; i1 < n; ++i1) for (int j1 = b; j1 < n; ++j1) if (abs(a[i1][j1]) % abs(a[i][j])) {
  150. if (abs(a[i1][j1]) % abs(a[i][j]) < m1) {
  151. m1 = abs(a[i1][j1]) % abs(a[i][j]);
  152. r = i;
  153. r1 = i1;
  154. c = j;
  155. c1 = j1;
  156. }
  157. }
  158. }
  159. }
  160. if (r1 == -1) {
  161. if (b != r) {
  162. row.push_back({b, r});
  163. model(a, row.back(), 0);
  164. //a[b].swap(a[r]);
  165. }
  166. if (b != c) {
  167. col.push_back({b, c});
  168. for (int i = 0; i < n; ++i)
  169. swap(a[i][b], a[i][c]);
  170. }
  171. for (int i = b + 1; i < n; ++i) {
  172. row.push_back({b, i, -a[i][b] / a[b][b]});
  173. model(a, row.back(), 0);
  174. assert(a[i][b] == 0);
  175. }
  176. for (int i = b + 1; i < n; ++i) {
  177. ll x = -a[b][i] / a[b][b];
  178. col.push_back({b, i, x});
  179. for (int j = 0; j < n; ++j) {
  180. a[j][i] += a[j][b]*x;
  181. }
  182. assert(a[b][i] == 0);
  183. }
  184. if (a[b][b] < 0) {
  185. row.push_back({b, -1});
  186. a[b][b] *= -1;
  187. }
  188. ++b;
  189. } else {
  190. assert(abs(a[r1][c1]) % abs(a[r][c]) == m1);
  191. if (r != r1 && c != c1) {
  192. assert(a[r1][c] % abs(a[r][c]) == 0);
  193. row.push_back({r, r1, -a[r1][c] / a[r][c] + 1});
  194. r = r1;
  195. model(a, row.back(), 0);
  196. }
  197. if (a[r][c] < 0) {
  198. row.push_back({r, -1});
  199. model(a, row.back(), 0);
  200. }
  201. if (a[r1][c1] < 0) {
  202. row.push_back({r1, -1});
  203. model(a, row.back(), 0);
  204. }
  205. if (r == r1) {
  206. ll x = -a[r][c1]/a[r][c]; //??
  207. col.push_back({c, c1, x});
  208. for (int i = 0; i < n; ++i)
  209. a[i][c1] += a[i][c]*x;
  210. } else {
  211. assert(c == c1);
  212. ll x = -a[r1][c]/a[r][c]; //??
  213. row.push_back({r, r1, x});
  214. for (int i = 0; i < n; ++i)
  215. a[r1][i] += a[r][i]*x;
  216. }
  217. //assert(abs(a[r1][c1]) == m1);
  218. }
  219. }
  220. vvl L = id(n), L1 = id(n), R = id(n), R1 = id(n);
  221. vvl test = a0;
  222. for (int i = 0; i < row.size(); ++i) {
  223. model(L1, row[row.size()-i-1], 1);
  224. model(L, row[i], 0);
  225. model(test, row[i], 0);
  226. }
  227. assert(test == mul(L, a0));
  228. for (int i = 0; i < col.size(); ++i) {
  229. model(R, col[i], 0);
  230. model(R1, col[col.size()-i-1], 1);
  231. }
  232. R = tr(R);
  233. R1 = tr(R1);
  234. out(L);
  235. out(L1);
  236. out(R);
  237. out(R1);
  238. assert(mul(L, L1) == id(n));
  239. assert(mul(R, R1) == id(n));
  240. assert(mul(mul(L, a0),R) == a);
  241. for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != j)
  242. assert(a[i][j] == 0);
  243. for (int i = 0; i+1 < n; ++i) {
  244. assert(a[i][i] == 0 || a[i+1][i+1] % a[i][i] == 0);
  245. assert(a[i][i] || a[i+1][i+1] == 0);
  246. }
  247. }
  248. return 0;
  249. }
  250.  
Success #stdin #stdout 0s 3112KB
stdin
Standard input is empty
stdout
Standard output is empty