HDU3571 N-dimensional Sphere(高斯消元 同模方程)

每个点到中心距离相等,以第0个点为参考,其他n个点到中心距等于点0到中心距,故可列n个方程

列出等式后二次未知数相消,得到线性方程组

将每个数加上1e17,求答案是再减去,求解时对一个2 * (1e17)以上的一个素数取模。

可用java 中高精度  System.out.println(BigInteger.valueOf(200000000000000001L).nextProbablePrime())  求一个大于2 * (1e17)的质数。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std; typedef long long LL;
const LL MOD = 200000000000000003ll, M = 100000000000000000ll;
const int N = 60; //System.out.println(BigInteger.valueOf(200000000000000001L).nextProbablePrime());
LL a[N][N];
LL MultMod(LL a,LL b){
a%=MOD;
b%=MOD;
LL ret=0;
while(b){
if(b&1){
ret+=a;
if(ret>=MOD) ret-=MOD;
}
a=a<<1;
if(a>=MOD) a-=MOD;
b=b>>1;
}
return (ret % MOD + MOD) % MOD;
}
LL Ext_gcd(LL a,LL b,LL &x,LL &y){//扩展欧几里得
if(b==0) { x=1, y=0; return a; }
LL ret= Ext_gcd(b,a%b,y,x);
y-= a/b*x;
return ret;
}
LL Inv(LL a, LL m){ ///求逆元
LL d,x,y, t = m;
d= Ext_gcd(a,t,x,y);
if(d==1) return (x%t+t)%t;
return -1;
} void gauss_jordan(LL A[][N], int n){
for(int i = 0; i < n; i++){
//选择一行r与第i行交换
int r = i;
for(int j = i; j < n; j++){
if(A[j][i]){
r = j;
break;
}
}
if(r != i){
for(int j = 0; j <= n; j++){
swap(A[r][j], A[i][j]);
}
}
for(int k = i + 1; k < n; k++){
if(A[k][i]){
LL x1 = A[k][i], x2 = A[i][i];
for(int j = n; j >= i; j--){
A[k][j] = ((MultMod(A[k][j], x2) - MultMod(x1, A[i][j])) % MOD + MOD) % MOD;
}
}
}
}
for(int i = n - 1; i >= 0; i--){
for(int j = i + 1; j < n; j++){
if(A[i][j]){
A[i][n] -= MultMod(A[j][n], A[i][j]);
if(A[i][n] < 0){
A[i][n] += MOD;
}
}
}
A[i][n] = MultMod(A[i][n], Inv(A[i][i], MOD));
}
} LL x[N];
int main(){
int t;
cin>>t;
for(int cas = 1; cas <= t; cas++){
int n;
cin>>n;
for(int i = 0; i < n; i++){
cin >> x[i];
x[i] += M;
}
for(int i = 0; i < n; i++){
a[i][n] = 0;
for(int j = 0; j < n; j++){
LL t;
cin >>t;
t += M;
a[i][n] += (MultMod(t, t) - MultMod(x[j], x[j]) + MOD) % MOD;
a[i][n] %= MOD;
a[i][j] = ((2 * t - 2 * x[j]) % MOD + MOD) % MOD;
}
}
gauss_jordan(a, n);
printf("Case %d:\n", cas);
for(int i = 0; i < n - 1; i++){
printf("%I64d ", a[i][n] - M); }
printf("%I64d\n", a[n - 1][n] - M); }
return 0;
}

  

上一篇:nginx 访问目录403


下一篇:[原创]一种基于Python爬虫和Lucene检索的垂直搜索引擎的实现方法介绍