Description

曾经有一个老掉牙的游戏放在我面前, 我没有珍惜. 直到这个游戏停产才追悔莫及. 人世间最痛苦的事情莫过于此, 如果上天给我一个再玩一次的机会, 我一定要, 通关!

如果你真的很想玩这个游戏, 那么就先看看我的题目吧, 搞不定这些的话是没办法通关的哟. 第一关其实很简单, 只有一个关闭的有密码锁的大门. 这大门上写着一个奇怪的算式, 估计 是要你利用它算出密码来开门吧 (果然是老掉牙的情节).

传说中这个式子中的 \(p\) 和 \(q\) 是两个奇质数, 等号右边算出来应该就是密码了吧, 你是 真的算不出来么?

\[\sum_{k=1}^{\frac{p-1}{2}} \lfloor \frac{kq}{p} \rfloor + \sum_{k=1}^{\frac{q-1}{2}} \lfloor \frac{kp}{q} \rfloor\]

Input

只有一行, 两个奇质数, 分别表示 \(p, q\).

Output

一个数, 表示算式结果.

Sample Input

5 7

Sample Output

6

Data Range

保证 \(p, q \leq 2^31-1\).

An Introduction to the Theory of Numbers 第 6 版定理 100

Explanation

据说这个定理是出自《数论导论》的......

然后想半天想不出来, 但总觉得形式比较漂亮 (雾), 最后只能翻题解:

打表找规律大法好 QwQ (CreationAugust)

这种就只能膜了...... 但是还有一些比较正常的, 例如:

原文链接:http://blog.csdn.net/czysjr/article/details/42360361

\(p = q\) 的情况就不用说了

\(p \neq q\) 时,

\(\frac{p}{q}\) 显然像一个斜率, 而下取整显然是就是这条直线下面点的数量.

这个看起来就和我的想法比较相近了, 然而最后还是打表=w=

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;

lli p, q;

int main(int argc, char** argv)
{
    scanf("%lld%lld", &p, &q);
    lli res = 0;
    if (p == q)
        res = (p + 1) * (p - 1) / 4;
    else
        res = (p - 1) * (q - 1) / 4;
    printf("%lld\n", res);
    return 0;
}