题目大意：给定T组数据，每组数据给定q和P，问直线x+y=q在第一象限形成的三角形内部有多少个整数点，结果对P

取模;

数据范围： 1≤T≤10
，1≤q≤1018， 1≤P≤1018

题目解答：俄罗斯乘法(复杂度：O(log2q)
) / Java大数取模(复杂度：O(1)) / 大数乘法取模转换为作差求余数(复杂度：O(1))
  原题实际上为求∑i=1q−2imodP=(q−2)∗(q−1)/2modP，由于q的范围很大，直接乘爆long long，采用俄罗斯乘法，或者用Java大数
  另外一种思路，由于a∗bmodp=a∗b−⌊a∗b/P⌋∗P ，⌊⌋

表示向下取整，可以把大数乘法取模转换为作差求余数

题目代码：
俄罗斯乘法

#include <cstdio>
#include <cstring>
#include <iostream>
#include <bitset>
using namespace std;//俄罗斯乘法（快速积）
long long mul(long long a, long long b, long long p)
{long long ans = 0;for(; b; b >>= 1){if(b & 1) ans = (ans + a) % p;a = a * 2 % p;}return ans;
}int main()
{int t;cin >> t;while(t--){long long q, p, ans;cin >> q >> p;if(q % 2)ans = mul((q-1)/2, q-2, p) % p;elseans = mul(q-1, (q-2)/2, p) % p;cout << ans << endl;}
}