djwj233 的博客

djwj233 的博客

【题解】P7847 「dWoi R2」Elevator / 电梯

posted on 2021-09-12 11:08:58 | under 题解 |

先把 $N=1$ 的情况特判掉,再进行讨论。

不难想到一个预处理前缀和的思路:我们对每个 $c$ 都算出其对应的方案数、答案,然后在方案数中累加上之前的所有方案数。

题目中那个式子可推得:$$ ab+ac=bc $$ 由于 $ac>0$,因此 $ab<bc$,有 $a<c$。

考虑一种暴力:我们对每个 $c$,暴力地枚举 $a\in [1,c)$,每次判断$$ b=\frac{ca}{c-a} $$ 是否为整数且是否有 $\gcd(a,b,c)=1$ 即可。复杂度 $\Theta(n^2)$。

问题在于如何优化这个枚举 $a$ 的过程。我们发现式子中的分母不太好处理,于是我们令 $c-a=x$,有$$ x\mid ca \Leftrightarrow x\mid c(c-x)\Leftrightarrow x\mid c^2-xc \Leftrightarrow x\mid c^2 $$ 又因为 $x\in [1,c)$,因此 $x$ 是 $c^2$ 的较小的因数,有 $x<\dfrac{c^2}{x}$。

那么由于 $\gcd(a,c)=\gcd(c-a,c)=\gcd(x,c)$,因此 $\gcd(a,b,c)=\gcd(\gcd(x,c),b)$。

又因为$$ b=\frac{c^2-xc}{x}=\frac{c^2}{x}-c $$ 因此设 $\gcd(x,c)=k$,则 $\gcd(k,b)=\gcd(k,\dfrac{c^2}{x})$。

再设 $\dfrac{x}{k}=\alpha,\dfrac{c}{k}=\beta$,有 $\gcd(\alpha,\beta)=1$,且$$ \gcd(k,\frac{k^2\beta^2}{k\alpha})=1\Rightarrow\gcd(k,\frac{k\beta^2}{\alpha})=1 $$ 由于 $\gcd(\alpha,\beta)=1$,所以 $\gcd(\alpha,\beta^2)=1$,有 $\alpha\mid k$。

若 $\alpha<k$,则 $\gcd(k,\dfrac{k}{\alpha})>1$,矛盾,因此有 $\alpha=k$,故 $x=\gcd(x,c)^2$。

另一方面,可以证明取任意 $x$ 使 $x=\gcd(x,c)^2$ 时,所得的 $b$ 都是整数且有 $\gcd(a,b,c)=1$。

那么现在的问题变得简单多了。由算术基本定理,我们对 $c$ 进行标准分解:(这可以通过素数筛实现)$$ c=\prod_{i=1}^{cnt} p_i^{a_i}\quad(p_i\in \mathbb P,a_i\ge1) $$ 那么我们取的 $\gcd(x,c)$ 质因数分解后第 $i$ 项的次幂要么是 $0$,要么是 $a_i$

对于第一问,看上去答案为 $2^{cnt}$,但这是不正确的。我们注意到有一个 $x<c$ 的要求,因此需要 $\gcd(x,c)^2<c$。

易知 $2^{cnt}$ 种答案一一对应地有 $>\sqrt{c}$ 和 $<\sqrt{c}$ 两种情况,且不可能有 $=\sqrt{n}$ 的情况出现。

因此答案就是 $2^{cnt-1}$。

对于第二问,让 $a$ 最小其实就是让 $x$ 最大。

那么我们反着来,枚举一个 $d=\gcd(x,c)$,枚举所有是 $d$ 的倍数且 $>d^2$ 的 $c$,逐一判断是否有 $\gcd(d^2,c)=1$ 并更新答案即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define il inline

typedef long long ll;

const int N=2000010;

int n;
int cnt[N]; ll f[N],ans[N];

void prework()
{
    for(int i=2;i<=n;i++) if(cnt[i]==0)
        for(int j=i;j<=n;j+=i)
            cnt[j]++;
    for(int i=2;i<=n;i++)
        f[i]=f[i-1]+(1LL<<(cnt[i]-1));

    for(int d=1;d*d<=n;d++)
        for(int c=d*(d+1);c<=n;c+=d)
            if(__gcd(c,d*d)==d)
                ans[c]=max(ans[c],(ll)d*d);
    for(int i=2;i<=n;i++) {
        ans[i]=i-ans[i]; // calculate a
        ans[i]=(ll)i*ans[i]/(i-ans[i]); // calculate b
    }
}

void solve()
{
    scanf("%d",&n);
    if(n==1) {
        puts("0");
    } else {
        printf("%lld %lld\n",f[n],ans[n]);
    }
}

int main()
{
    n = N-10;
    prework();

    int T; cin>>T;
    while(T--) solve();

    return 0;
}