Wannafly挑战赛14 A-直角三棱锥

链接：https://www.nowcoder.com/acm/contest/81/A

来源：牛客网

题目描述

在三维空间中，平面 x = 0, y = 0, z = 0，以及平面 x + y + z = K 围成了一个三棱锥。

整天与整数打交道的小明希望知道这个三棱锥内、上整点的数目。

他觉得数量可能很多，所以答案需要对给定的 M 取模。

输入描述:

输入有 1 ≤ T ≤ 105 组数据。

每组数据中，输入两个整数 0 ≤ K ≤ 109 + 7, 1 ≤ M ≤ 109 + 7，意义如题目描述。

输出描述:

对于每组数据，输出一个整数，为三棱锥内、上整点的数目对 M 取模。

示例1

输入

4
0 60
1 60
29 60
29 100007

输出

1
4
40
4960

---

思路

算法即是数学！结果显然为：

ans=(N+1)(N+2)(N+3)6%K

AC代码

#include <iostream>
typedef long long ll;
using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--){
        ll K,M;
        cin >> K >> M;
        ll a=K+1,b=K+2,c=K+3;
        ll ans = (a*b%(6*M)*c%(6*M)/6);
        cout << ans << endl;
    }
    return 0;
}