这题的关键是q为质数，不妨设线段上点(x0, y0)，则x0+y0=q。

那么直线方程则为y = y0/x0x，如果存在点(x1, y1)在此直线上，

那么y1 = y0*x1/x0，而y0 = q-x0，

于是y1 = (q-x0)*x1/x0 = q*x1/x0-x1，

因为x0 < q，于是(x0, q) = 1，

于是x0 | x1，

而x1 < x0，于是x1 = x0，

也就是说三角形内部的整点都不在线上，

于是计算三角形内部的整点即可。

但是中间计算数据很大，需要用大数，这里采用了Java。

 

代码：

import java.math.BigInteger;import java.util.Scanner;public class Main{    public static void main(String[] args)    {        Scanner input = new Scanner(System.in);        int T = input.nextInt();        BigInteger p, q;        BigInteger two = new BigInteger("2");        BigInteger one = new BigInteger("1");        for (int times = 1; times <= T; ++times)        {            q = input.nextBigInteger();            p = input.nextBigInteger();            q = q.subtract(two);            q = q.multiply(q.add(one));            q = q.divide(two);            System.out.println(q.mod(p));        }    }}