题解 P4132 【[BJOI2012]算不出的等式】

一只书虫仔 · 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

类欧几里得算法。

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

然后题目作者良心的帮我们省掉了 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