看到这个式子就感觉很有意思
左边就是求一次函数 $y=\left \lfloor \frac{q}{p} \right \rfloor x$ 在 $x \in [0,(p-1)/2]$ 时函数图像下方的整点数量
右边就是求一次函数 $y=\left \lfloor \frac{p}{q} \right \rfloor x$ 在 $x \in [0,(q-1)/2]$ 时函数图像下方的整点数量
把两个图画出来，发现图像刚好可以拼接成一个 $(p-1)/2\ \cdot\ (q-1)/2$ 的矩形，又因为 $p,q$ 互质所以两个图像在范围内不会经过整点
所以答案就是矩形中的整点数：$(p-1)/2\ \cdot\ (q-1)/2$ ？
但是还要考虑一下 $p=q$ 时的情况，此时还要再加上 $(p-1)/2$，加起来化简一下就是 $(pq-1)/4$
然后就行了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> using namespace std; typedef long long ll; typedef long double ldb; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } ll p,q; int main() { p=read(),q=read(); printf("%lld\n",p==q ? (p*q-1)/4 : (p-1)/2*(q-1)/2); return 0; }
原文：https://www.cnblogs.com/LLTYYC/p/11284661.html