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
#include
#include
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=0;i--)
	{
		g=extEculid(h[i][i],p,x,y);//由于p是质数，所以g实际上等于1
		ans[i]=calcu(x,h[i][n]);
		for(j=0;j