Elevator / 电梯

· · 个人记录

验题人做法

验题人可能更具有第一次做这道题的思维方式的代表性，所以先贴一下验题人的思路：

第一问

\frac{1}{a}-\frac{1}{b}=\frac{1}{c} bc-ac-ab=0 c^2+bc-ac-ab=c^2 (c-a)(c+b)=c^2

对于一个 c 满足这此式的 (a,b) 个数 f[c] 就是 \lfloor \dfrac{d(c^2)}{2}\rfloor（d 表示约数个数函数）。注意需要满足 \gcd(a,b,c)=1，因此对每个 c 的倍数 kc(k\ge2) 都要让 f[kc] 减去一个 f[c]。最后做一个前缀和即可。时间复杂度为 O(n\log n+T)。

第二问

\frac{1}{a}-\frac{1}{b}=\frac{1}{c} \Leftrightarrow bc=a(b+c) \Leftrightarrow a=\frac{bc}{b+c} \because \gcd(a,b,c)=1 \therefore \gcd(\frac{bc}{b+c},b,c)=1 \gcd(\frac{bc}{b+c},\gcd(b,c))=1

设 b=m\times\gcd(b,c),c=n\times \gcd(b,c)，\gcd(m,n)=1

则有：

\gcd(\frac{mn}{m+n}\times \gcd(b,c),\gcd(b,c))=1 \therefore \gcd(b,c) \mid (n+m)

而 \gcd(mn,m+n)=1，\dfrac{mn}{m+n}\times \gcd(b,c) 是整数，那么 (m+n)\mid\gcd(b,c)。

\therefore n+m=\gcd(b,c) \therefore b+c=\gcd(b,c)*(n+m)=\gcd(b,c)^2

预处理时枚举 \gcd(b,c)，枚举它的所有倍数作为 c，计算出 b 后更新答案。由于涉及到调和级数枚举以及内部求 \gcd，时间复杂度 O(n\ln n\log n+T)。

需要引起注意的是 b 的范围，存在爆 int 的情况，这也是为什么出题人要大家求 b。

参考代码

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N = 2e6 + 5;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch & 15);
        ch = getchar();
    }
    return x * f;
}
int primes[N], cnt;
int v[N];
void seive(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (v[i] == 0)
        {
            v[i] = i;
            primes[++cnt] = i;
        }
        for (int j = 1; j <= cnt; ++j)
        {
            if (primes[j] > n / i || primes[j] > v[i]) break;
            v[primes[j] * i] = primes[j];
        }
    }
}
int calc(int x)
{
    int res = 1;
    while (x > 1)
    {
        int p = v[x], cnt = 1;
        x /= p;
        while (x % p == 0) ++cnt, x /= p;
        res = res * (cnt * 2 + 1);
    }
    return res / 2;
}
int ans[N];
int ans2[N];
void init()
{
    seive(N - 1);
    for (int i = 2; i < N; ++i)
    {
        ans[i] = calc(i);
    }
    for (int i = 2; i < N; ++i)
    {
        for (int j = i * 2; j < N; j += i) ans[j] -= ans[i];
    }
    for (int i = 2; i < N; ++i)
    {
        ans[i] += ans[i - 1];
    }
    memset(ans2, 0x3f, sizeof ans2);
    for (int gcd = 2; gcd < N; ++gcd)
    {
        int temp = min(gcd * gcd, N);
        for (int c = gcd; c < temp; c += gcd)
        {
            int b = gcd * gcd - c;
            if (__gcd(b, c) != gcd) continue;
            ans2[c] = min(ans2[c], b);
        }
    }
}
signed main()
{
    init();
    int t = read();
    while (t--)
    {
        int n = read();
        if (n == 1ll) puts("0");
        else printf("%lld %lld\n", ans[n], ans2[n]);
    }
    return 0;
}

出题人做法

出题人的做法对这两问并不是割裂开来的，它们是一起求出来的。本来这道题也没有分两问的分数，不过在出题团队的建议下给了部分分，还是很人性化的吧~

这里也贴一下部分分吧。

30分

暴力枚举 30\% 数据范围的答案即可。

还一种情况就是按验题人做法的第一问。

30+21分

就是前两个做法的融合。

70分

这题虽然看起来很简单，但是做起来还是有一定的难度的。原因在于我们需要用数学证明进行辅助。

根据原式变形：

\dfrac{b-a}{ab} = \dfrac{1}{c} (b-a)(c-a) = a^2

我们假设 b-a=m^2p,\;c-a=n^2p，其中 m,n,p 均为正整数。那么就有 a=mnp。

又根据 b-a=m^2p 得到 b=m^2p+mnp，于是 p 为 b 的因数。

同理，p 也是 c 的因数。

但是题目说 \gcd(a,b,c)=1 ，那么 p 必须是 1。

因此，b-a 和 c-a 均为完全平方数（关键）。

有了这个以后，我们就可以仅用 O(\sqrt{N}) 的复杂度来枚举 a 了。但是仍然要验证得到的 a,b,c 是否互质。

这样的复杂度可以变为 O(N^{1.5}\log N+T)。

满分算法

虽然复杂度已经很低了，但是仍然不能解决这道题。

注意到 b=\dfrac{ac}{c-a}，那么必然要有 (c-a)|ac。假设我们在枚举时，枚举完全平方数 k^2=c-a，那么就会有 b = \dfrac{(c-k^2)c}{k^2}。由于 k^2|k^2c，所以必需要 k|c。

这里我们回头看证明，会发现这个 k 就是 n，且 \gcd(m, n)=1。那么算法就呼之欲出了，显然是用离线算法。

首先，对于因子 1 我们可以单独处理。然后，对 n 从 2 开始枚举，一直到 \sqrt{N}，而 m 则从 1 开始枚举，同时保证 \gcd(m, n)=1。最后，根据

a=mn,\;\; c=n(m+n)

就可以轻松计算出 a,c，并对此时的 c 值答案贡献 +1，更新此时的最小的 a。一旦 c>N 则退出循环。

这里其实你可以发现：顺序枚举时，每次对 a 更新，最后一次更新的 a 正好是最小的 a。

这并不难证明，因为 c=nm+n^2=a+n^2，由于 n 呈递增，如果 c 不变，那么 a 一定递减。

从效果上分析时间复杂度：

对于某一个 N，由于

m=\sum_{i=1}^{\sqrt{N}}\dfrac{N}{i}-i\approx N\sum_{i=1}^{\sqrt{N}}\dfrac{1}{i}

根据调和级数的增长性质得到

\sum_{i=1}^{\sqrt{N}}\dfrac{1}{i}\approx \ln \sqrt N

于是最终的复杂度就是 O(N\log ^2 N+T)。

要特别注意的是，因为题目求的是 b，所以存在爆 int 的情况，这也是我为什么要让大家求 b 而不是求 a 了~

当然，由于代码对某些不必要跑 \gcd 的情况分开来了，而且测评机跑得快，加上这里面的 log 本来就不大，所以 500ms 不到就跑完了。

代码如下

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e6+5;
int ans[maxn], ansa[maxn];

int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}

int main()
{
    register int i, j, n, m;
    int r, T, N;
    int flag;
    long long a, b, c;
    N = maxn-5;
    for(i = 2; i <= N; i += 1) ///单独处理 n=1 的情况
        ans[i] = 1, ansa[i] = i-1;
    for(j = 2; j <= N; j += 4) ///单独处理 n=2 的情况
    {
        n = 4+j;
        if(n > N)
            break;
        ans[n] += 1;
        ansa[n] = j;
    }
    r = sqrt(N);
    for(n = 3; n <= r; n += 1)///这就是我们要枚举的 n
    {
        flag = n * n;
        m = 0;
        while(++m)///这是我们要枚举的 m
        {
            if(gcd(n, m) != 1)
                continue;
            j = n * m;
            i = flag + j;
            if(i > N)
                break;
            ans[i] += 1;
            ansa[i] = j;
        }
    }
    for(i = 3; i <= N; i += 1)///前缀求和得到答案
        ans[i] += ans[i-1];
    scanf("%d", &T);
    for(i = 0; i < T; i += 1)
    {
        scanf("%d", &N);
        if(N > 1)
            printf("%d %lld\n", ans[N], 1ll*ansa[N]*N/(N-ansa[N]));///long long不能忘
        else
            printf("0\n");
    }
    return 0;
}