题解 CF142A 【Help Farmer】
VenusM1nT
2020-10-26 19:03:43
想多了,看到题面以为是道结论题。
![一姬海滩派对表情1.png](https://i.loli.net/2020/10/26/lYDh4FAm1CTgW27.png)
然后找了一下规律,发现最大值恒为 $9\times (n+1)-n$,此处可以考虑形如已知 $xy=r$ 求 $x$ 最大值的情况,肯定是一个极大一个极小,放到这题也是一样,而两个 $+2$ 肯定是给 $1$ 的贡献更大,所以答案就是上面那个式子。
然后尝试推最小值,依然考虑上面那个 $xy=r$,肯定是 $x,y$ 最相近的时候取到最小,那么问题来了:这个最相近怎么取
![杏树契约表情2.png](https://i.loli.net/2020/10/26/YNHr3dfAMnmX6ta.png)
因为有三个数,所以并不会,转而考虑枚举因数,根据网上查阅发现 2e9 内数最多有约 1500 个因数,所以 $\text{O}(m^2)$ 是可以接受的,于是枚举两个因数,唯一确定第三个数,取最小值即可。
~~貌似 1e18 以内最多有 1e5 个因数,如果哪位可以找到最小值的结论就可以出增强版了(可能已经有了也说不定)~~
```cpp
#include<bits/stdc++.h>
#define N 100000
#define reg register
#define inl inline
#define int long long
using namespace std;
int n,a[N+5],tot,ans=1e18,Ans;
signed main()
{
scanf("%lld",&n);
Ans=3*3*(n+1)-n;
a[++tot]=1;
a[++tot]=n;
for(reg int i=2;i<=(int)(sqrt(n));i++)
{
if(!(n%i))
{
a[++tot]=i;
if(i*i!=n) a[++tot]=n/i;
}
}
for(reg int i=1;i<=tot;i++)
{
for(reg int j=1;j<=tot;j++)
{
reg int x=a[i],y=a[j],z=n/a[i]/a[j];
if(n%(x*y)) continue;
if(x*y*z!=n) continue;
ans=min(ans,(x+1)*(y+2)*(z+2));
}
}
ans-=n;
printf("%lld %lld\n",ans,Ans);
return 0;
}
```