bzoj2659 [Beijing wc2012]算不出的算式

给定$p,q$,求$\sum_{k=1}^{\frac{p-1}{2}} \lfloor{\frac{kq}{p}} \rfloor + \sum_{l=1}^{\frac{q-1}{2}}\lfloor \frac{lp}{q} \rfloor$ ,其中$p,q$是奇数且是质数。

这个式子其实可以将$k,l​$看作$x​$,那么这个式子相当于$y=\frac{q}{p} x​$和$y=\frac{p}{q}x​$这两条直线上每个横坐标上对应的纵坐标下第一个整点到$x​$轴的垂线的线段长度之和,实际上也就是在$k \in [1,\lfloor \frac{p-1}{2} \rfloor]​$和$l \in [1,\lfloor \frac{q-1}{2} \rfloor]​$时这两条直线下的纵坐标为正的整点个数。

gr

于是答案实际上是长方形${(0,\frac{p-1}{2}),(\frac{q-1}{2},\frac{p-1}{2}),(\frac{q-1}{2},0),(0,0)}$内的整点个数,需要注意的事当$p=q$时对角线上的整点会被计算两次,加上即可。

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll p,q;
scanf("%lld%lld",&p,&q);
if(p==q) printf("%lld\n",(p-1)*(p-1)/4+(p-1)/2);
else printf("%lld\n",(p-1)/2*(q-1)/2);
return 0;
}