题解 P4132 【[BJOI2012]算不出的等式】

题目链接

Solution [BJOI2012]算不出的等式

题目大意：给定奇质数(p,q)，求(sum_{k=1}^{frac{p-1}{2}}lfloorfrac{kp}{q} floor+sum_{k=1}^{frac{q-1}{2}}lfloorfrac{kq}{p} floor)

---

分析：

问题实质上是在求([1,frac{p-1}{2}])区间内一次函数(y=frac{p}{q}x)下的整点个数（后半部分同理）

然后我们发现后半部分就是交换了(p,q)，那么旋转一下就相当于(y=frac{p}{q}x)上面的整点个数

两个互补，就相当于长宽分别为(frac{p-1}{2}),(frac{q-1}{2})矩形内的整点个数

然鹅发现如果(p=q)的话就gg了，如果(p=q)，答案为(frac{p^2-1}{4})

#include <iostream>
using namespace std;
long long a,b;
int main(){
	cin >> a >> b;
	if(a != b)cout << (a / 2) * (b / 2) << endl;
	else cout << (a * a - 1) / 4 << endl;
	return 0;
}