#include #include // vector는 일종의 list입니다. 원소를 뒤에 추가하는 작업에 용이합니다. 사용을 array처럼 할 수 있습니다. #include // abs(절댓값), max(최댓값) 등의 함수가 포함된 헤더입니다. typedef struct { int p[3]; } tiii; // tiii는 3개의 int형 변수를 담고 있는 자료형이며, 벡터를 나타냅니다. using namespace std; // vector, abs, max 등의 앞에 std::를 붙여주는 역할입니다. vector l[124], extd[124]; // l[n]과 extd[n]은 길이가 n인 벡터들을 모아놓은 list입니다. 즉, 리스트가 124개 있는 것입니다. void push(int N, int a[3]) { int i; tiii tmp; for (i = 0; i<3; i++) tmp.p[i] = a[i]; // a[i]를 우리가 다루는 형태인 tiii로 변환합니다. extd[N].push_back(tmp); // extd[N].push_back(tmp)는, extd[N]이라는 list의 맨 뒤에 tmp를 추가하는 것입니다. // 예를 들면, extd[N]이 {v1, v2}였다면, 새로운 extd[N]은 {v1, v2, tmp}가 됩니다. // 이 부분은 모든 성분이 0 이상인 벡터를 추가하는 것입니다. if (a[0] == 0) { // 첫 번째 원소가 0인 경우 if (a[1]>0 && a[2]>0) { // (0,0,x)나 (0,x,0)꼴은 부호를 바꾸면 정확히 반대되는 벡터이므로 더 추가하지 않습니다. tmp.p[2] = -tmp.p[2]; extd[N].push_back(tmp); // (0,x,y)와 (0,x,-y)만 추가하는 것입니다. (0,-x,y)=-(0,x,-y)이므로 추가하지 않습니다. } } else { if (a[1] == 0) { // 첫 번째 원소가 0이 아니고 두 번째 원소가 0인 경우 if (a[2]>0) { // (x,0,0)꼴은 부호를 바꾸면 정확히 반대되는 벡터이므로 더 추가하지 않습니다. tmp.p[2] = -tmp.p[2]; extd[N].push_back(tmp); // (x,0,y)와 (x,0,-y)만 추가하는 것입니다. } } else { if (a[2] == 0) { // 마지막 원소만 0이고 나머지는 0이 아닌 경우 tmp.p[1] = -tmp.p[1]; extd[N].push_back(tmp); // (x,y,0)와 (x,-y,0)만 추가하는 것입니다. } else { // 모든 원소가 0이 아닌 경우. (x,y,z)라 합시다. tmp.p[2] = -tmp.p[2]; extd[N].push_back(tmp); // (x,y,-z) tmp.p[1] = -tmp.p[1]; extd[N].push_back(tmp); // (x,-y,-z) tmp.p[2] = -tmp.p[2]; extd[N].push_back(tmp); // (x,-y,z) // 이렇게 4개를 추가합니다. 첫 성분이 -x인 경우들은 모두 이들의 부호를 바꾼 것으로 나타낼 수 있습니다. } } } } // 벡터의 가능한 부호 형태를 모두 extd[N]에 추가합니다. 단, (x,y,z)와 (-x,-y,-z)가 동시에 추가되지는 않도록 합니다. int inpro(tiii x, tiii y) { return x.p[0] * y.p[0] + x.p[1] * y.p[1] + x.p[2] * y.p[2]; } // 내적 bool check(int N, int a, int b, int c) { if (inpro(extd[N][a], extd[N][b]) != 0) return false; if (inpro(extd[N][b], extd[N][c]) != 0) return false; if (inpro(extd[N][c], extd[N][a]) != 0) return false; return true; } // extd[N][a], extd[N][b], extd[N][c] 3개의 벡터가 서로 수직인지 확인합니다. int main() { int i, j, k, n, x, y, z, s, adj, ss, NNN; // i,j,k,n은 루프문을 위한 변수입니다. x,y,z는 정육면체가 들어가는 직육면체의 크기를 나타냅니다. long long ans = 0LL, inc; // ans는 우리가 구하려는 문제의 답입니다. int zzzz[3]; tiii temp; freopen("output.txt", "w+", stdout); // 출력 내용이 많은 관계로, 다른 파일에 출력하였습니다. for (n = 1; n<124; n++) { printf("n = %d\n", n); for (i = 0; i <= n; i++) { for (j = 0; j <= i; j++) { for (k = 0; k <= j; k++) { if (i*i + j * j + k * k == n * n) { // 길이가 n인 벡터 (i,j,k) temp.p[0] = i; temp.p[1] = j; temp.p[2] = k; l[n].push_back(temp); if (i == j) { // (i,i,k) 형태 zzzz[0] = i; zzzz[1] = j; zzzz[2] = k; push(n, zzzz); // (i,i,k)와 부호 바꾼 것들 zzzz[1] = k; zzzz[2] = i; push(n, zzzz); // (i,k,i)와...(이하 동일) zzzz[0] = k; zzzz[1] = i; push(n, zzzz); // (k,i,i) } else if (j == k) { // (i,j,j) 형태 zzzz[0] = i; zzzz[1] = j; zzzz[2] = k; push(n, zzzz); // (i,j,j) zzzz[0] = k; zzzz[1] = i; push(n, zzzz); // (j,i,j) zzzz[1] = k; zzzz[2] = i; push(n, zzzz); // (j,j,i) } else { // (i,j,k) 형태 zzzz[0] = i; zzzz[1] = j; zzzz[2] = k; next_permutation(zzzz, zzzz + 3); do { push(n, zzzz); } while (next_permutation(zzzz, zzzz + 3)); //next_permutation을 한 번씩 해주면, 가능한 모든 6가지에 대해 실행합니다. } //printf("l[%d][%d] = (%d, %d, %d)\n",n,(int)l[n].size()-1,i,j,k); } } } } // 길이가 자연수인 모든 벡터 찾기(l[n]에는 대표 벡터((i,j,k) i>=j>=k>=0), extd[n]에는 모든 벡터(단, (a,b,c)와 (-a,-b,-c)는 같은 것으로 취급) 포함) s = (int)l[n].size(); ss = (int)extd[n].size(); //for(i=0;i