题解 CF142A 【Help Farmer】

VenusM1nT

2020-10-26 19:03:43

Solution

想多了,看到题面以为是道结论题。 ![一姬海滩派对表情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; } ```