题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5666
让我们先看看这道题目的官方题解
1002
考虑一条以(0,0)为起点,(x,y)为终点的线段上格点的个数（不包含端点时）,一定是gcd(x,y)?1,这个很显然吧.
然后整个网格图范围内的格点数目是?2??q?(q?1)??.
所以答案就是?2??q?(q?1)??? 所有线段上的格点的个数.
因为gcd(a,b)=gcd(a,b?a) (b>a),所以gcd(x,y)=gcd(x,p?x)=gcd(x,p),p是质数,所以gcd(x,y)=1,所以线段上都没有格点,所以答案就是?2??q?(q?1)??.
这就是官方的解释，其实在这个公式推导上并没有什么问题，很容易想到的是在这个三角形内部的点，但是这道题目的一个关键还在这个大数据，凭着找到了一组大数据的质数，小编我在组内hack了7个人，直接加了700分(这波简直不亏)，因为long long的数据范围是到2^63，大概就是10^18次方，如果不用大数处理或者不用快速幂类的方法肯定会炸long long，这里小编就介绍一下快速幂类的方法。
我们要求的是q*(q-1)/2这个数，相当于我们要求(q-1)/2个q的和(这里还需要判断一下奇偶)，仔细回想一下快速幂的用法，快速幂是快速处理一个数的n次幂的，也就是n个数的积，如果我们这里把这个积改成和，就和快速幂一样能够快速解决这个问题，因为快速幂的每一步都会取模，所以也不用担心会出现炸long long的情况。
#include <cstdio>
#define LL __int64
LL fast_mul(LL a, LL b, LL p)
{LL ret = 0; while(b) { if(b & 1) ret = (ret + a) % p; a = (a + a) % p;b >>= 1; } return ret % p;
}
int main()
{int t;LL x,y,ans;scanf("%d",&t);while (t--){scanf("%I64d%I64d",&x,&y);if ((x-2)%2==0) ans = fast_mul((x-2)/2,x-1,y);else ans = fast_mul((x-2),(x-1)/2,y);printf("%I64d\n",ans);}
}