CF1375I Cubic Lattice

2022/5/1 6:15:09

编程Tag： text GCD cubic frac cdot Lattice overrightarrow qua CF1375I

本文主要是介绍CF1375I Cubic Lattice，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

简要题意：

定义三维空间中的一个 lattice 是满足下列条件的三维整点的集合：

\[L=\{u\cdot \overrightarrow{r_1}+v\cdot \overrightarrow{r_2}+w\cdot \overrightarrow{r_3} \}_{u,v,w\in \mathbb Z} \]

其中 $\overrightarrow{r_1},\overrightarrow{r_2},\overrightarrow{r_3}$ 为三维空间中的整系数坐标向量，满足：

$\overrightarrow{r_1},\overrightarrow{r_2},\overrightarrow{r_3}$ 两两正交，即

\[\overrightarrow{r_1}\cdot \overrightarrow{r_2}=\overrightarrow{r_1}\cdot \overrightarrow{r_3} =\overrightarrow{r_2}\cdot \overrightarrow{r_3}=0 \]

$\overrightarrow{r_1},\overrightarrow{r_2},\overrightarrow{r_3}$ 长度相等，即

\[|\overrightarrow{r_1}|=|\overrightarrow{r_2}|=|\overrightarrow{r_3}| \]

现在由有 $n$ 个三维整点构成的的集合 $A=\{\overrightarrow{a_1},\overrightarrow{a_2},\cdots,\overrightarrow{a_n} \}$ ，其中 $\overrightarrow{a_i}=(x_i,y_i,z_i)$。

你需要找到一个 lattice L 满足 $A⊂ L$ 且组成 $L$ 的三个基向量尽可能大。

sol：

二维平面上的变换一般使用复数来刻画，其中相当于整数在实数中地位的，被称为 Gauss 整数（即 $a+b\text{i}$ 其中 $a,b\in \mathbb Z$）。所有 Gauss 整数关于 $+$ 和 $\times$ 的算构成一个 Euclid 整环。

先考虑一个简化的二维版本：

可以发现所有 $a_i$ 可以被拆成两个高斯整数的乘积，即 $a_i=b_i\cdot g$，其中 $g=(\overrightarrow{r_1},\overrightarrow{r_2})$。而要找到最大的 $g$ 可以直接通过 Euclid 算法完成。

然后来考虑三维空间：

根据第一个条件，可以发现 $\overrightarrow{r_3}$ 与 $\overrightarrow{r_1}\times \overrightarrow{r_2}$ 是共线向量。

而又因为 $|\overrightarrow{r_1}\times \overrightarrow{r_2}|=r^2,|\overrightarrow{r_3}|=r$，说明 $\overrightarrow{r_1}\times \overrightarrow{r_2}=\pm r\cdot \overrightarrow{r_3}⇒ r\in \mathbb N^{*}$ 。

（即 $\overrightarrow{r_3}$ 可以用 $\overrightarrow{r_3}=\pm \frac{\overrightarrow{r_1}\cdot \overrightarrow{r_2}}{|r_1|} $ 表示）

并且，由于 $\overrightarrow{a}=u\cdot \overrightarrow{r_1}+v\cdot \overrightarrow{r_2}+w\cdot \overrightarrow{r_3}$，则 $|\overrightarrow{a}|^2=(u^2+v^2+w^2)\cdot r^2⇒r^2 |(|\overrightarrow{a}|^2)$

即 $r$ 需要满足 $r^2|\gcd(x_1^2+y_1^2+z_1^2,x_2^2+y_2^2+z_2^2,\cdots ,x_n^2+y_n^2+z_n^2)$。

并且因为满足这个条件的 $r$ 数量不多，所以可以对 $r$ 从大到小逐个检验是否合法。

而在三维空间中的变换，一般使用四元数 $a+b\text{i}+c\text{j}+d\text{k}$ 来刻画，而在四元数中有整数地位的，被称为 Lipschitz 四元数。（四元数的运算满足结合律，不满足交换律，$\text i^2=\text j ^2 =\text k ^2=ijk=-1$

但是这样定义出来的四元数集合不构成 Euclid 整环，而这道题中的操作类似于 $\gcd$ 的过程，因此需要扩充一下定义，考虑增加部分有理四元数。

在复数中，$|a+b\text i|=\sqrt{a^2+b^2}$，会有一些满足 $a^2+b^2\in\mathbb Z$，这样就会有一些形如 $\frac 4 5+\frac 3 5 \text i$ 的东西，虽然模长为整数，但是可以和 $1,\text i$ 整系数表示出 $\frac{1+\text i}{5}$，模长就不为整数。

于是在 $\mathbb C$ 中，如果能扩充的话，肯定要考虑 $a+b\text i$，其中 $\frac 1 a,\frac 1 b\in{\mathbb Z}$。那么在这种情况情况下，除了 $a=b=1$，其余所有的有理复数模长均不等于 $1$，因此不能扩充。

但是，这件事搬到四元数 $\mathbb H$ 中就不一样了，可以发现 $a=b=c=d=2$ 时，$|\frac{1+\text i +\text j +\text k}2|=1$。

因此，如果将 $\omega=\frac{1+\text i+\text j+\text k}2$ 加入 Lipschitz 四元数集合，并取正系数表示，就得到了Hurwitz 四元数：

\[H=\{a+b\text i+c\text j+d\text k|a,b,c,d\in \mathbb{Z}\vee a,b,c,d\in\mathbb Z+\frac 1 2 \} \]

可以证明，虽然没有交换律，但是 $H$ 中依然有类似地唯一分解定理，可以做 Euclid 算法。

具体地，在 $H$ 中，对于两个数 $A,B$，可以定义它的左商、左余数，右商、右余数，以及左 $\gcd$ 和右 $\gcd$。如，左商和左余数对应表达式 $A=qB+r$，而左 $\gcd $ 就表示模最大的 $d$ 满足 $A=du,B=dv$。

有了 Hurwitz 四元数后，整个问题就清晰了很多：

首先对于三维空间中的向量 $\overrightarrow a=(x,y,z)$ ，对应到四元数 $A=x\text i+y\text j+z\text k$。那么三维空间中其中一组标准的正交基就可以表示为 $\text{i,j,k}$。

根据立体几何，三维空间中的旋转变换可以这样表示：

\[\overrightarrow{v}↦k\cdot \frac{q\cdot \overrightarrow v\cdot \overline q}{q\cdot \overline q}=k\cdot \frac{q\cdot \overrightarrow v\cdot \overline q}{|q|^2} \]

其中 $\overrightarrow v$ 表示实部为 $0$ 的四元数，$q=a+b\text i+c\text j+d\text k$ 为一个特定的四元数，$\overline q$ 为 $q$ 的共轭 $\overline q=a-b\text i -c\text j-d\text k$。

于是，$\overrightarrow{r_1},\overrightarrow{r_2},\overrightarrow{r_3}$ 都可以看成标准正交基经过某个旋转并缩放后的结果，因此有：

\[\begin{cases} \overrightarrow{r_1} =r\cdot \frac{q\cdot \text i\cdot \overline{q}}{|q|^2}\\ \overrightarrow{r_2} =r\cdot \frac{q\cdot \text j\cdot \overline{q}}{|q|^2}\\ \overrightarrow{r_3} =r\cdot \frac{q\cdot \text k\cdot \overline{q}}{|q|^2}\\ \end{cases} \]

然后可以发现 $x=\frac{k}{|q|^2}=\frac{k}{a^2+b^2+c^2+d^2}$ 的分母是 $4$ 的约数。

具体证明：

首先还是这个式子 $\overrightarrow{v}↦k\cdot \frac{q\cdot \overrightarrow v\cdot \overline q}{q\cdot \overline q}$。

考虑写成矩阵形式：

\[\frac{k}{a^2+b^2+c^2+d^2}\cdot \begin{pmatrix} a^2+b^2-c^2-d^2 & 2cb-2ad & 2ac+2bd\\ 2ad+2bc & a^2-b^2+c^2-d^2 & 2cd-2ab\\ 2bd-2ac & 2ab+2cd & a^2-b^2-c^2+d^2\\ \end{pmatrix} \]

显然矩阵中所有元素均为整数。因此分数 $\frac{k}{a^2+b^2+c^2+d^2}$ 应该整除于所有矩阵元素。不失一般性，可以假设 $\gcd(a,b,c,d)=1$（否则可以让 $a,b,c,d$ 除以这个数使四元数坐标减小，并且矩阵元素不变）。假设 $\frac{k}{a^2+b^2+c^2+d^2}=\frac{P}{Q}$，则 $Q$ 要整除于所有矩阵元素，并且整除于 $a^2 +b^2+c^2+d^2$，即整除于：

\[\gcd \begin{pmatrix} a^2+b^2+c^2+d^2\\ a^2+b^2-c^2-d^2 \\ a^2-b^2+c^2-d^2 \\ a^2-b^2-c^2+d^2 \end{pmatrix} =\gcd \begin{pmatrix} a^2+b^2+c^2+d^2\\ 2(c^2+d^2) \\ 2(b^2+d^2) \\ 2(b^2+c^2) \end{pmatrix} =\gcd \begin{pmatrix} a^2+b^2+c^2+d^2\\ 2(c^2+d^2) \\ 2(b^2+d^2) \\ 4d^2 \end{pmatrix} \]

（$\gcd(a\pm b,b)=\gcd(a,b)=\gcd(-a,b)$）

并且由于 $\gcd(a,b)$ 整除于 $\gcd(k\cdot a,b)$，因此 $Q$ 整除于：

\[\gcd \begin{pmatrix} 4(a^2+b^2+c^2+d^2)\\ 4(c^2+d^2) \\ 2(b^2+d^2) \\ 4d^2 \end{pmatrix} =4\gcd (a^2,b^2,c^2,d^2)=4 \]

因此 $\overrightarrow{v}↦k\cdot \frac{q\cdot \overrightarrow v\cdot \overline q}{4}$。

如果放宽条件 $x\in H$，则进一步可说明 $x$ 的分母是 $2$ 的约数，即 $2x\in\mathbb Z$。通过适当调整使得 $q$ 为 Lipschitz 四元数，根据题目条件可得到 $x=1$。

定义 $f(v)=q\cdot v\cdot \overline{q}$，那么存在一组向量 $\overrightarrow{b_1},\overrightarrow{b_2},\cdots,\overrightarrow{b_n}$ 满足

\[\overrightarrow{a_i}=f(\overrightarrow{b_i})=q\cdot \overrightarrow{b_i} \cdot \overline{q} \]

于是，此时有 $q|\overrightarrow{a_i}$ ，因此 $q|\gcd(\overrightarrow{a_1},\overrightarrow{a_2},\cdots,\overrightarrow{a_n})$。

并且还枚举了 $r$，因此必须有 $|q|^2=r$，由唯一分解定理可得到 $q|r$。

于是 $q|\gcd(\overrightarrow{a_1},\overrightarrow{a_2},\cdots,\overrightarrow{a_n},r)$。事实上，设 $q_0=\gcd(\overrightarrow{a_1},\overrightarrow{a_2},\cdots,\overrightarrow{a_n},r)$ ，则 $|q_0|^2|r$，因此只有当 $|q_0|^2=r$ 时才有必要验证下去。

之后就只需要反解出 $\overrightarrow{b_i}=\frac{q\cdot \overrightarrow{a_i}\cdot \overline q}{r^2}$ 并检验是否是整数即可。

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define R(i,a,b) for(int i=(a),i##E=(b);i<=i##E;i++)
#define L(i,a,b) for(int i=(b),i##E=(a);i>=i##E;i--)
const ld eps=1e-10l;
using namespace std;

struct qua
{
	ld a,b,c,d;
	inline qua(ld A=0,ld B=0,ld C=0,ld D=0):a(A),b(B),c(C),d(D) {}
	inline qua operator + (qua A) 
	{
		return qua(a+A.a,b+A.b,c+A.c,d+A.d);
	}
	inline qua operator - (qua A)
	{
		return qua(a-A.a,b-A.b,c-A.c,d-A.d);
	}
	inline qua operator * (qua A)
	{
		return qua(
			a*A.a-b*A.b-c*A.c-d*A.d,
			a*A.b+b*A.a+c*A.d-d*A.c,
			a*A.c-b*A.d+c*A.a+d*A.b,
			a*A.d+b*A.c-c*A.b+d*A.a
		);
	}
	inline qua conj()//共轭
	{
		return qua(a,-b,-c,-d);
	}
	inline ld norm()//|q|^2
	{
		return a*a+b*b+c*c+d*d;
	}
	inline qua inv()
	{
		return conj()*qua(1.l/norm());
	}
	inline int check_int()
	{
		return fabsl(roundl(a)-a)<eps&&fabsl(roundl(b)-b)<eps&&fabsl(roundl(c)-c)<eps&&fabsl(roundl(d)-d)<eps;
	}
	inline qua qround()
	{
		qua q1=qua(roundl(a),roundl(b),roundl(c),roundl(d));
		qua q2=qua(floorl(a)+.5l,floorl(b)+.5l,floorl(c)+.5l,floorl(d)+.5l);
		return (q1-*this).norm()<(q2-*this).norm()?q1:q2;
	}
	inline qua operator / (qua A)
	{
		return A.inv() * *this;
	}
	inline qua operator % (qua A)
	{
		qua ret=(*this/A).qround();
		return *this-A*ret;
	}
	inline void printf()
	{
		cout<<b<<" "<<c<<" "<<d<<'\n';
	}
	inline void print()
	{
		cout<<llroundl(b)<<" "<<llroundl(c)<<" "<<llroundl(d)<<'\n';
	}
}a[11111],g;
qua gcd(qua a,qua b)
{
	return b.norm()<eps?a:gcd(b,a%b);
}
ll gcd(ll a,ll b)
{
	return !b?a:gcd(b,a%b);
}

int n;
ll G;
vector<ll>v;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	R(i,1,n)
	{
		cin>>a[i].b>>a[i].c>>a[i].d;

		g=gcd(g,a[i]);
		G=gcd(G,(ll)a[i].norm());
	}
	for(ll i=1;i*i<=G;i++) if(G%(i*i)==0) v.emplace_back(i);
	reverse(v.begin(),v.end());
	for(auto x:v)
	{
		qua q=gcd(g,qua(x));
		ll r=(ll)q.norm();
		if(r!=x) continue;
		qua q0=q.conj() / qua(r * r);
		int ok=1;
		R(i,1,n) if((q0*a[i]*q).check_int()==0)
		{
			ok=0;
			break;
		}
		if(ok)
		{
			cout<<r*r<<'\n';
			(q*qua(0,1)*q.conj()).print();
			(q*qua(0,0,1)*q.conj()).print();
			(q*qua(0,0,0,1)*q.conj()).print();
			return 0;
		} 
	}
}

这篇关于CF1375I Cubic Lattice的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

CF1375I Cubic Lattice

相关编程文章