b113. 6. 性系求解＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2011-08-24 13:33:32| 人1,182| 回0 | 上一篇 | 下一篇

b113. 6. 性系求解

推 0 收藏 0 0 站台

b113. 6. 性系求解

容：

入明：

出明：

本因果限任一出不太好定是否正，

所以若果限的，出N即可。

改多，

完第一值n後，

後面的方程式到EOF做束。

(MAPLEWING 2011/01/19修正)

例入：

[Input 1] <-粹明是第的，在的入面有。 3 2 8 4 2 2 5 1 5 4 10 -1 1 [Input 2] 3 1 2 3 0 8 10 12 6 7 8 9 6 [Input 3] 3 1 2 3 0 4 5 6 3 7 8 9 0 [Input 4] 1 3 10

例出：

[Output 1] <-粹明是第的，您不用出西。 1 x1 = 11 x2 = -4 x3 = 3 [Output 2] N [Output 3] 0 [Output 4] 1 x1 = 10/3

提示：

出：

93全科能力

作法 : 模高斯消元,

特注意型的, 可能分掉, 以免溢位,
最後用了 long long 才

/**********************************************************************************/
/* Problem: b113 "6. 性系求解" from 93全科能力   */
/* Language: C                                                                   */
/* Result: AC (0ms, 208KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-08-24 13:29:55                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct {
   long long ele, den;/*ele/den*/
}Fraction;
Fraction Matrix[52][52];
long long GCD(long long x, long long y) {
   long long t;
   while(x%y) {
       t = x, x = y, y = t%y;
   }
   return y;
}
Fraction F_mod(Fraction A) {/*modify*/
   if(A.ele < 0 && A.den < 0)
       A.ele *= -1, A.den *= -1;
   if(A.ele > 0 && A.den < 0)
       A.ele *= -1, A.den *= -1;
   return A;
}
Fraction F_divid(Fraction A, Fraction B) {
   Fraction C;
   C.ele = A.ele * B.den;
   C.den = A.den * B.ele;
   if(C.ele == 0) {
       C.den = 1;
       return C;
   }
   long long t = GCD(fabs(C.ele), fabs(C.den));
   C.ele /= t, C.den /= t;
   C = F_mod(C);
   return C;
}
Fraction F_multi(Fraction A, Fraction B) {
   Fraction C;
   if(A.ele == 0 || B.ele == 0) {
       C.ele = 0, C.den = 1;
       return C;
   }
   long long t = GCD(fabs(A.ele), fabs(B.den));
   A.ele /= t, B.den /= t;
   t = GCD(fabs(A.den), fabs(B.ele));
   A.den /= t, B.ele /= t;
   C.ele = A.ele * B.ele;
   C.den = A.den * B.den;
   C = F_mod(C);
   return C;
}
Fraction F_addit(Fraction A, Fraction B) {
   long long t = A.den/GCD(A.den, B.den)*B.den;
   Fraction C;
   C.ele = A.ele*(t/A.den) + B.ele*(t/B.den);
   C.den = t;
   t = GCD(fabs(C.ele), fabs(C.den));
   C.ele /= t, C.den /= t;
   C = F_mod(C);
   return C;
}
Fraction F_minus(Fraction A, Fraction B) {
   long long t = A.den/GCD(A.den, B.den)*B.den;
   Fraction C;
   C.ele = A.ele*(t/A.den) - B.ele*(t/B.den);
   C.den = t;
   t = GCD(fabs(C.ele), fabs(C.den));
   C.ele /= t, C.den /= t;
   C = F_mod(C);
   return C;
}
void Print(int n) {
   int a, b;
   for(a = 0; a < n; a++) {
       for(b = 0; b <= n; b++)
           printf("(%3lld/%3lld) ", Matrix[a][b].ele, Matrix[a][b].den);
       puts("");
   }
}
main() {
   int n, a, b, c;
   scanf("%d", &n);
       for(a = 0; a < n; a++) {
           for(b = 0; b <= n; b++)
               scanf("%lld", &Matrix[a][b].ele), Matrix[a][b].den = 1;
       }
       int Flag = 0;
       for(a = 0; a < n; a++) {
           int Idx = -1;
           for(b = a; b < n; b++)
               if(Matrix[b][a].ele)
                   {Idx = b;break;}
           if(Idx == -1) {continue;}
           Fraction tmp;/*Swap*/
           for(b = 0; b <= n; b++)   {
               tmp = Matrix[a][b];
               Matrix[a][b] = Matrix[Idx][b];
               Matrix[Idx][b] = tmp;
           }
           Idx = a;
           for(b = 0; b < n; b++) {
               if(b == Idx) continue;
               Fraction X = F_divid(Matrix[b][a], Matrix[Idx][a]);
               for(c = 0; c <= n; c++) {
                   Matrix[b][c] = F_minus(Matrix[b][c], F_multi(Matrix[Idx][c], X));
               }
           }
       }
       int time = 0;
       for(a = 0; a < n; a++) {
           int flag1 = 0;
           if(Matrix[a][a].ele)
               time++, flag1 = 1;
           if(flag1 == 0 && Matrix[a][n].ele)
               {Flag = 1;break;}
       }
       if(time < n && Flag == 0)   Flag = 2;
       if(Flag == 0) {
           Fraction Ans[n];
           for(a = n-1; a >= 0; a--) {
               Fraction sum;
               sum.ele = 0, sum.den = 1;
               for(b = a+1; b < n; b++)
                   sum = F_addit(sum, F_multi(Ans[b], Matrix[a][b]));
               sum = F_minus(Matrix[a][n], sum);
               Ans[a] = F_divid(sum, Matrix[a][a]);
           }
           puts("1");
           for(a = 0; a < n; a++) {
               printf("x%d = ", a+1);
               if(Ans[a].den == 1)   printf("%lld", Ans[a].ele);
               else   printf("%lld/%lld", Ans[a].ele, Ans[a].den);
               puts("");
           }
       } else if(Flag == 1) {
           puts("0");
       } else
           puts("N");
   return 0;
}