首页 > 代码库 > POJ 1166 The Clocks 高斯消元 + exgcd(纯属瞎搞)
POJ 1166 The Clocks 高斯消元 + exgcd(纯属瞎搞)
根据题意可构造出方程组,方程组的每个方程格式均为:C1*x1 + C2*x2 + ...... + C9*x9 = sum + 4*ki;
高斯消元构造上三角矩阵,以最后一个一行为例:
C*x9 = sum + 4*k,exgcd求出符合范围的x9,其他方程在代入已知的变量后格式亦如此。
第一发Gauss,蛮激动的。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #include <ctime> #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f #define Mod 6000007 using namespace std; const int MAXN = 20; int up[] = {0,4,3,4,3,5,3,4,3,4}; int site[10][5] = { {0}, {1,2,4,5}, {1,2,3}, {2,3,5,6}, {1,4,7}, {2,4,5,6,8}, {3,6,9}, {4,5,7,8}, {7,8,9}, {5,6,8,9} }; int Map[10]; LL coe[MAXN][MAXN]; LL sol[MAXN]; void Output() { int i,j; for(i = 1;i <= 9; ++i) { for(j = 1;j <= 10; ++j) { printf("%lld ",coe[i][j]); if(j == 9) printf("= "); } printf("\n"); } puts(""); } LL Abs(LL x) { if(x < 0) return -x; return x; } LL gcd(LL x,LL y) { if(y == 0) return x; return gcd(y,x%y); } void exgcd(LL a,LL b,LL &x,LL &y) { if(b == 0) x = 1,y = 0; else { LL x1,y1; exgcd(b,a%b,x1,y1); x = y1; y = x1-a/b*y1; } } //n为行数,m为列数(包含最后一项) //return -1无整数解 return 0存在整数解。 int Gauss(int n,int m) { int i,j,k; LL T,A,B; //Output(); for(i = 1;i < n; ++i) { for(j = i+1;j <= n; ++j) { if(coe[j][i] == 0) continue; if(coe[i][i] == 0) { for(k = i;k <= m; ++k) T = coe[i][k],coe[i][k] = coe[j][k],coe[j][k] = T; continue; } T = gcd(coe[i][i],coe[j][i]); A = coe[j][i]/T,B = coe[i][i]/T; for(k = i;k <= m; ++k) coe[j][k] = coe[i][k]*A - coe[j][k]*B; } //Output(); } LL sum = 0; for(i = n;i >= 1; --i) { sum = coe[i][m]; for(j = m-1;j > i; --j) sum -= coe[i][j]*sol[j]; LL A = coe[i][i],B = 4,C = sum; LL x,y; exgcd(A,B,x,y); //cout<<"A = "<<A<<" B = "<<B<<" C = "<<C<<" x = "<<x<<" y = "<<y<<endl; x *= C/gcd(A,B); //cout<<"x = "<<x<<endl; y = B/gcd(A,B); x = (x-x/y*y + Abs(y))%Abs(y); sol[i] = x; //cout<<"i = "<<i<<" x = "<<x<<endl; // if(sum%coe[i][i] != 0) // return -1;//此时无整数解 // sol[i] = sum/coe[i][i]; } return 0; } int main() { int i,j; for(i = 1;i <= 9; ++i) scanf("%d",&Map[i]); memset(coe,0,sizeof(coe)); for(i = 1;i <= 9; ++i) { for(j = 0;j < up[i]; ++j) { coe[site[i][j]][i] = 1; } } for(i = 1;i <= 9; ++i) coe[i][10] = (4-Map[i])%4; if(-1 == Gauss(9,10)) while(0) ; bool mark = true; for(i = 1;i <= 9;++i) { for(j = 0;j < sol[i]; ++j) { if(mark == false) printf(" "); else mark = false; printf("%d",i); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。