HOJ 5666 Segment（快速乘法）

快速乘法
题目意思：
判断直线x+y=q与坐标轴围成的三角形“内”的整数点的个数 很容易推出公式 （q-1）*（q-2）/2

本题要点：
1、 long long的范围， q 是素数， q - 1 是偶数（q > 2）. 用 (q - 1) / 2。 记 x = (q - 1) / 2, y = q - 2；
2、 用 快速乘法计算 mod p 的乘积， 类似于快速幂。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int T;
long long q, p;long long quick_multi(long long a, long long b)
{
    long long ans = 0;while(b){
    if(b & 1)ans = (ans + a) % p;a = (a + a) % p;b >>= 1;}return ans;
}int main()
{
    scanf("%d", &T);while(T--){
    scanf("%lld%lld", &q, &p);if(2 == q){
    printf("0\n");continue;}long long x = (q - 1) / 2, y = q - 2;x %= p, y %= p;printf("%lld\n", quick_multi(x, y));}return 0;
}/* 1 2 107 *//* 0 */