Contents

1. 1. 题目：
2. 2. 分析：

题目：

分析：

• 把直角坐标系画出来就知道了
  格点可以是长方形的也可以是正方形的
  -公式：(1 + (q - 2)) * (q - 2) / 2

=> (q - 1) * (q - 2) / 2

c++版

#include <cstdio>

long long qmul(long long a, long long b, long long mod){

    long long ans = 0;
    while(b){
        if(b & 1)
            ans = (ans + a) % mod;
        a = (a << 1) % mod;
        b >>= 1;
    }
    return ans;
}

int main(int argc, char* argv[]){

    int T;
    long long q, p, a, b;
    scanf("%d", &T);
    while(T--){
        scanf("%I64d%I64d", &q, &p);
        a = q - 1;
        b = q - 2;
        a >>= 1; // a或b除2都行
        printf("%I64d\n", qmul(a, b, p));
    }
    return 0;
}

java版

//直接用java里处理大数的包，不过速度似乎有点慢，看了下别人用c++大数模板提交的
//代码0MS，而java的在300MS左右
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int t = sc.nextInt();
      for (int i = 0; i < t; ++i) {
        BigInteger n = sc.nextBigInteger();
        BigInteger mod = sc.nextBigInteger();
        if (n.compareTo(new BigInteger("3")) < 0)
          System.out.println(0);
        else {
          BigInteger ans = n.subtract(new BigInteger("1"));
          ans = ans.multiply(n.subtract(new BigInteger("2")));
          ans = ans.divide(new BigInteger("2"));
          System.out.println(ans.mod(mod));
        }
          
      }
    }
}