HDU 3571 N-dimensional Sphere（高斯消元 數論題）

這道題算是比較綜合的了，要用到擴展歐幾裡得，乘法二分，高斯消元。

看了題解才做出來orz

基本思路是這樣，建一個n*(n-1)的行列式，然後高斯消元。

關鍵就是在建行列式時會暴long long，所以要用取模來計算，即公式ax=b，等價於ax=b(mod p)

因為答案范圍不超過正負10^17次，p可以取（2*10^17+3）。

然後加減乘除都能夠進行了，乘法用乘法二分來做，除法用模線性方程求逆來做。

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define LL __int64
const LL p=(LL)200000000*1000000000+3;//杭電的編譯器不能直接寫200000000000000003，會ce
const LL L=(LL)100000000*1000000000;
LL ans[60],a[60][60],h[60][60];
int n;
LL modans(LL s)//取模
{
	if(s<0)
		s=s+p;
	else if(s>=p)
		s=s-p;
	return s;
}
LL calcu(LL base,LL tmp)//乘法二分
{
    LL ans=0;
	while(tmp)
	{
		if(tmp&1)ans=modans(ans+base);
		base=modans(base*2);
		tmp/=2;
	}
	return ans;
}
void get_h(int s)//每一行初始化
{
	int i,j;
	LL tmp=0;
	for(i=0;i<n;i++)
	{
		h[s][i]=modans(2*(a[s][i]-a[s+1][i]));
		tmp+=calcu(a[s][i],a[s][i])-calcu(a[s+1][i],a[s+1][i]);
		tmp=modans(tmp);
	    //printf("%I64d ",h[s][i]);
	}
	h[s][n]=tmp;
	//printf("%I64d\n",h[s][n]);
}
void init()
{
	int i,j;
	for(i=0;i<n;i++)
		get_h(i);
}
LL extEculid(LL a,LL b,LL &x,LL &y)
{
	LL tmp,d;
	if(b==0){x=1;y=0;return a;}
	d=extEculid(b,a%b,x,y);
	tmp=x;x=y;y=tmp-a/b*y;
	return d;
}
void solve()
{
	int i,j,k;
	for(i=0;i<n;i++)//這一步不能落下，當第i行第i個數是0時，要與下面的行互換。這題數據貌似有點水，要是互換後第i個數還是0，就會出錯了。。。
	{
		for(j=0;j<n;j++)
			if(h[i][j])
				break;
		if(i<j)
		{
			for(k=0;k<=n;k++)
				swap(h[i][k],h[j][k]);
		}
	}
	for(i=0;i<n-1;i++)
	{
	  
	  for(j=i+1;j<n;j++)
	  {
		int tmp=h[i][j];
		for(k=i+1;k<=n;k++)
			h[j][k]=modans(calcu(h[j][k],h[i][i])-calcu(h[i][k],h[j][i]));
	  }
	}
	LL x,y,g;
	for(i=n-1;i>=0;i--)
	{
		g=extEculid(h[i][i],p,x,y);//由於p是質數，所以g實際上等於1
		ans[i]=calcu(x,h[i][n]);
		for(j=0;j<i;j++)
			h[j][n]=modans(h[j][n]-calcu(h[j][i],ans[i]));
	}
}
int main()
{
	int t,i,j;
	scanf("%d",&t);
	for(int k=1;k<=t;k++)
	{
		scanf("%d",&n);
		for(i=0;i<=n;i++)
		for(j=0;j<n;j++)
		{
			scanf("%I64d",&a[i][j]);
			a[i][j]+=L;
		}
                init();
		solve();
		printf("Case %d:\n",k);
		printf("%I64d",(ans[0]-L)%L);
		for(i=1;i<n;i++)
          printf(" %I64d",(ans[i]-L)%L);
		printf("\n");
	}
	return 0;
}