【题解】P7847 「dWoi R2」Elevator / 电梯
djwj233
2021-09-12 11:08:58
先把 $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$ 并更新答案即可。
代码：
```c++
#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;
}
```