本文共 2071 字，大约阅读时间需要 6 分钟。
依据题意可构造出方程组。方程组的每一个方程格式均为：C1*x1 + C2*x2 + ...... + C9*x9 = sum + 4*ki;
高斯消元构造上三角矩阵，以最后一个一行为例：
C*x9 = sum + 4*k。exgcd求出符合范围的x9，其它方程在代入已知的变量后格式亦如此。
第一发Gauss。蛮激动的。
#include #include #include #include #include #include #include #include #include #include #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 6000007using 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 = "< <<" B = "<<<" C = "< <<" x = "< <<" y = "< < <= 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;}
转载地址：http://nkdia.baihongyu.com/