模-gcd直角三棱锥

题目：

链接：https://ac.nowcoder.com/acm/problem/15705 来源：牛客网

在三维空间中，平面 x = 0, y = 0, z = 0，以及平面 x + y + z = K 围成了一个三棱锥。 整天与整数打交道的小明希望知道这个三棱锥内、上整点的数目。 他觉得数量可能很多，所以答案需要对给定的 M 取模。

#include <stdio.h>
int main()
{
    long long k,t,i,j,q;
    scanf("%lld\n",&t);
    long long a[t][2];
    long long b[t];
    for(i=0;i<t;i++)
        for(j=0;j<2;j++) scanf("%lld",&a[i][j]);
    for(i=0;i<t;i++)
    {
        k=a[i][0];   //分成k+1个直角三角形，每个直角三角形（i^2+i）/2 —— i表示边长
        q=a[i][1];  //整数个数
        b[i]=((k+3)%(6*q)*(k+2)%(6*q)*(k+1)%(6*q))/6;
    }
    for(i=0;i<t;i++) printf("%lld\n",b[i]);
}

解题思路

由题目x+y+z=k，得出当k>0，是一个截距相同的截面，而后又限制x>0,y>0,z>0，可以得到一个直角三人锥。

题目要求得到三棱锥上、内的整数坐标的个数，故，可以将直角三人锥拆成k+1个直角三角形（每个边长不一样，i表示边长）。

先看单个直角三角形的整数个数：+

：把直角三角形拼成正方形，计算该正方形的所有整数个数
+：把斜线上的数再加一边，以便除2

再看所有直角三角形之和：i=1,2,3……k+1 （求和）从0开始数，有k+1个直角三角形

化简之后可得

坑：取模 (a/b)%c=(a%bc)/b

当(n+1)(n+2)(n+3)相乘，范围可能会爆掉，所以要在之前取模，而取模可能会影响到除法的操作，m*=6，就会使最后结果不变