P0941

[Beijing wc2012]算不出的算式

[Beijing wc2012]算不出的算式

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

如果你真的很想玩这个游戏，就先来解决下面的问题。游戏的第一关只有一扇关闭的密码门，门上写着一个奇怪的算式。你需要计算出这个算式的值，作为打开大门的密码。

已知 pp 和 qq 是两个奇质数，请计算：

∑i=1(p−1)/2⌊iqp⌋+∑j=1(q−1)/2⌊jpq⌋.\sum_{i=1}^{(p-1)/2}\left\lfloor\frac{iq}{p}\right\rfloor + \sum_{j=1}^{(q-1)/2}\left\lfloor\frac{jp}{q}\right\rfloor.

其中，⌊x⌋\lfloor x\rfloor 表示不超过 xx 的最大整数。

输入格式

输入仅一行，包含两个奇质数 p,qp,q。

输出格式

输出一个整数，表示上述算式的值。

样例输入

5 7

样例输出

6

数据范围

  • p,qp,q 均在 3232 位有符号整数范围内；
  • p,qp,q 均为奇质数。

来源与许可

本题为 Beijing WC 2012 试题「算不出的算式」，题面与测试数据整理自 BZOJ。

样例 1

输入

5 7

输出

6