自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 21:56:49，当前版本为作者最后更新于2020-09-25 11:47:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Description

给定两个奇质数 $p,q$，求：

$$\sum\limits_{i=1}^{\frac{p-1}{2}}\left\lfloor\dfrac{iq}{p}\right\rfloor+\sum\limits_{j=1}^\frac{q-1}{2}\left\lfloor\dfrac{jp}{q}\right\rfloor $$

Solution 1

类欧几里得算法。

我们知道类欧的基本式子为：

$$\sum\limits_{i=0}^n\left\lfloor\dfrac{ai+b}{c}\right\rfloor $$

然后题目作者良心的帮我们省掉了 $b$，所以我们只需要将 $b=0$ 代进去即可。

代码就不放了（其实是写锅了 /kk）

Solution 2

类欧明显不配蓝题，所以这题还有找规律做法。

比如我们看样例，$\dfrac{p-1}{2}=2$，$\dfrac{q-1}{2}=3$，$2 \times 3=6$，所以我们能猜到输出 $\dfrac{p-1}{2} \times \dfrac{q-1}{2}$ 即可。

Code 2

#include <bits/stdc++.h>

using namespace std;

int main () {
	long long p, q;
	scanf("%lld%lld", &p, &q);
	p = (p - 1) / 2;
	q = (q - 1) / 2;
	printf("%lld", p * q);
	return 0;
}

然后你会发现只有 $90$ 分，有一个点 WA 掉了。

Solution 2 - For Addition

$p=q$ 的时候要特判，这个时候的答案应该是 $\dfrac{p^2}{4}$。

Code 2 - For Addition

#include <bits/stdc++.h>

using namespace std;

int main () {
	long long p, q;
	scanf("%lld%lld", &p, &q);
	if (p == q) {
		printf("%lld", p * p / 4);
		return 0;
	}
	p = (p - 1) / 2;
	q = (q - 1) / 2;
	printf("%lld", p * q);
	return 0;
}

然后就会 A 了。