有多少正方体满足如下条件:
八个顶点的坐标均为整数,且范围在1到2021之间(包含两端)
问题也可以被描述为:
假设集合A为{ (x,y,z) | 1<=x,y,z<=2021 且 x,y,z为整数 },从集合A中选8个点组成一个正方体,有多少种选取方法?
注意答案不是1到2020的立方和,因为正方体可以斜过来。本人最好的做法也需要n^4,n=2021时约1e14。方法是考虑选三个向量满足三向量互相垂直,然后试着把它塞进去。向量只需枚举前两个,第三个可以计算出来。前两个向量又只需枚举4个值,就可以通过一些方法计算出剩下两个,故为n^4。有没有更好的方法?