题目地址：洛谷：【P4132】[BJOI2012]算不出的等式 – 洛谷、BZOJ：Problem 2659. — [Beijing wc2012]算不出的算式

题目描述

如果你真的很想玩这个游戏，那么就先看看我的题目吧，搞不定这些的话是没办法通关的哟。第一关其实很简单，只有一个关闭的有密码锁的大门。这大门上写着一个奇怪的算式，估计是要你利用它算出密码来开门吧（果然是老掉牙的情节）。
传说中这个式子中的p和q是两个奇质数，等号右边算出来应该就是密码了吧，你是真的算不出来么？
\sum_{k=1}^{\frac{p-1}{2}} \left\lfloor \frac{kq}{p} \right\rfloor + \sum_{l=1}^{\frac{q-1}{2}} \left\lfloor \frac{lp}{q} \right\rfloor =

输入输出格式

输入格式：
只有一行，两个奇质数，分别表示p,q。

输出格式：
一个数,表示算式结果。

输入输出样例

输入样例#1：

5 7

输出样例#1：

6

说明

p,q在32位整型范围内。

题解

我们来观察一个\sum_{k=1}^{\frac{p-1}{2}} \left\lfloor \frac{kq}{p} \right\rfloor有什么意义。我们可以把它转化为在横坐标范围只有 \left\lfloor \frac{p}{2} \right\rfloor ，纵坐标范围只有 \left\lfloor \frac{q}{2} \right\rfloor 的坐标系中，在直线y = \frac{q}{p} x下方的坐标中不含0的整点数目。
分别考察本题加号两边的两项，可以发现第二项只是把第一项对应的坐标系旋转倒置了一下，其答案应该等于第一项，即该坐标系中的所有整点数。这个答案是\left\lfloor \frac{p}{2} \right\rfloor \left\lfloor \frac{q}{2} \right\rfloor。
但是当p与q相等的时候，直线y=x上的整点被计算了两遍，即此时的答案应该是 \left\lfloor \frac{p}{2} \right\rfloor (\left\lfloor \frac{p}{2} \right\rfloor + 1) 。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

LL p, q;

int main() {
    p = readint(); q = readint();
    printf("%lld", (p / 2) * (q / 2) + (p == q ? p / 2 : 0));
    return 0;
}