数的拆分的题解

给定正整数 n, k，请将 n 写成 k 个正整数的乘积，要求这 k 个数的和尽可能小。输出这
个最小的和。

搜索

这是最基本的搜索。有 4040 分。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
int n,k;
int dfs(int n,int k){
	if(k==1)return n;
	int ans=INT_MAX;
	for(int i=1;i<=n;i++){
		if(n%i==0)ans=min(ans,min(i+dfs(n/i,k-1),n/i+dfs(i,k-1)));
	}return ans;
}
int main(){
	read(n);read(k);
	cout<<dfs(n,k);
	return 0;
}

之后，有 22 种方法，先介绍第 11 种。

第 11 种

这个是标程的方法，最终效果会比我的方法慢，但是代码极为简短。

首先，对于上面的代码，可以加上记忆化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
int n,k;
map<int,map<int,int> >mp;
int dfs(int n,int k){
	if(k==1)return n;
	if(mp[n][k])return mp[n][k];
	int ans=INT_MAX;
	for(int i=1;i<=n;i++){
		if(n%i==0)ans=min(ans,min(i+dfs(n/i,k-1),n/i+dfs(i,k-1)));
	}return mp[n][k]=ans;
}
int main(){
	read(n);read(k);
	cout<<dfs(n,k);
	return 0;
}

依旧只有 4040 分。

继续优化，我们发现枚举约数可以优化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
int n,k;
map<int,map<int,int> >mp;
int dfs(int n,int k){
	if(k==1)return n;
	if(mp[n][k])return mp[n][k];
	int ans=INT_MAX;
	for(int i=1;i*i<=n;i++){
		if(n%i==0)ans=min(ans,min(i+dfs(n/i,k-1),n/i+dfs(i,k-1)));
	}return mp[n][k]=ans;
}
int main(){
	read(n);read(k);
	cout<<dfs(n,k);
	return 0;
}

这样就有 8080 分了。

还可以在哪里优化呢？

我们发现 kk 很大，而 nn 的质因子个数并不多。

可以证明（显然）nn 的质因子小于 log⁡nlog {n}

那么 kk 这么大，显然就是有很多很多的 11。

可以让i从 22 开始。

Q：如果是质数怎么办？返回INT_MAX显然是错的。

A：所以我们需要把ans的初值赋成n+k-1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
int n,k;
map<int,map<int,int> >mp;
int dfs(int n,int k){
	if(k==1)return n;
	if(mp[n][k])return mp[n][k];
	int ans=n+k-1;
	for(int i=2;i*i<=n;i++){
		if(n%i==0)ans=min(ans,min(i+dfs(n/i,k-1),n/i+dfs(i,k-1)));
	}return mp[n][k]=ans;
}
int main(){
	read(n);read(k);
	cout<<dfs(n,k);
	return 0;
}

这样就有100分了。

最大的点跑了0.234s

第 22 种

我们先增加一个参数l，让后面的数字全部要≥geql。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
int n,k;
ll dfs(int l,int n,int k){
	if(k==1)return n;
	ll ans=INT_MAX;//可能会炸出负数，所以要long long
	for(int i=l;i<=n;i++){
		if(n%i==0)ans=min(ans,i+dfs(i,n/i,k-1));
	}return ans;
}
int main(){
	read(n);read(k);
	cout<<dfs(1,n,k);
	return 0;
}

依旧只有 4040 分。

继续优化，我们发现可以加记忆化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
map<int,map<int,map<int,int> > >mp;
int n,k;
ll dfs(int l,int n,int k){
	if(k==1)return n;
	if(mp[l][n][k])return mp[l][n][k];
	ll ans=INT_MAX;
	for(int i=l;i<=n;i++){//这里
		if(n%i==0)ans=min(ans,i+dfs(i,n/i,k-1));
	}return mp[l][n][k]=ans;
}
int main(){
	read(n);read(k);
	cout<<dfs(1,n,k);
	return 0;
}

依旧是 4040 分qwqqwq。。。

继续优化，我们发现枚举约数可以优化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
int n,k;
ll dfs(int l,int n,int k){
	if(k==1)return n;
	ll ans=INT_MAX;
	for(int i=l;i*i<=n;i++){
		if(n%i==0)ans=min(ans,i+dfs(i,n/i,k-1));
	}return ans;
}
int main(){
	read(n);read(k);
	cout<<dfs(1,n,k);
	return 0;
}

这样就有 8080 分了。

还可以在哪里优化呢？

我们发现 kk 很大，而 nn 的质因子个数并不多。

可以证明（显然）nn 的质因子小于 log⁡nlog {n}

那么 kk 这么大，显然就是有很多很多的 11。

我们可以让l从 22 开始。

Q：如果是质数怎么办？返回INT_MAX显然是错的。

A：所以我们需要把ans的初值赋成n+k-1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
int n,k;
ll dfs(int l,int n,int k){
	if(k==1)return n;
	ll ans=n+k-1;
	for(int i=l;i*i<=n;i++){
		if(n%i==0)ans=min(ans,i+dfs(i,n/i,k-1));
	}return ans;
}
int main(){
	read(n);read(k);
	cout<<dfs(2,n,k);
	return 0;
}

这样就有100分了。

最大的点跑了0.093s

也算是一个很大的突破。

Q：还有哪里可以优化吗？

A：其实还是有的。

我们看 dfsdfs 里的 ii。由于 ii 是保证单调不下降的，所以 ik≤ni^{k}leq n

这样的话，我们可以用到快速幂的方法。

但是，你会发现，这个是假的，因为我们把 1 放到了最后处理，所以此优化和上面的优化不可兼用，我们把上面的优化拿掉。

当然，因为 kk 过大，我们还得压缩一下 kk 的范围。

七七八八的优化搞到最后，代码差不多是这样的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
ll n,k,x=1,L=1,R=35,s;
ll pw(ll x,ll y){
	ll ans=1;
	while(y){
		if(y&1)ans=ans*x;
		y>>=1;
		x=x*x;
	}return ans;
}
map<int,map<int,map<int,int> > >mp;
ll dfs(ll l,ll n,ll k){
	if(k==1)return n;
	if(n==1)return k;
	if(mp[l][n][k])return mp[l][n][k];
	ll ans=INT_MAX;
	ll Lft=l-1,Rgt=10000;
	while(Lft+1<Rgt){
		ll Mid=(Lft+Rgt)>>1;
		if(pow(Mid,k)<=n)Lft=Mid;
		else Rgt=Mid;
	}
	for(ll i=l;i<=Lft;i++){
		if(n%i==0)ans=min(ans,i+dfs(i,n/i,k-1));
	}return mp[l][n][k]=ans;
}
int main(){
	read(n);read(k);
	int x=n;
	for(int i=2;i*i<=n;i++)
		while(x%i==0)x/=i,s++;
	if(x)s++;
	if(k>s)cout<<dfs(1ll,n,s)+k-s;
	else cout<<dfs(1ll,n,k);
	return 0;
}

最大的点跑了0.106s。

当然最后的用时也差不多。

实际上，我们问题想回来，如果 kk 过于大，方法肯定是唯一的。

因为 x,y≥2x,y geq 2 的情况下 x×y≥x+yx imes y geq x+y。所以，最优解显然是 nn 的质因子和 ++ (k(k −- nn 的质因子个数 ))。

我们可以这样写一下。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
int n,k,s;
int pw(int x,int y){
	int ans=1;
	while(y){
		if(y&1)ans=ans*x;
		y>>=1;
		x=x*x;
	}return ans;
}
map<int,map<int,map<int,int> > >mp;
int dfs(int l,int n,int k){
	if(k==1)return n;
	if(mp[l][n][k])return mp[l][n][k];
	int ans=n+k-1,Lft=l-1,Rgt=100;
	while(Lft+1<Rgt){//这边的话，明显是有二分性的，所以直接二分。
		ll Mid=(Lft+Rgt)>>1;
		if(pow(Mid,k)<=n)Lft=Mid;
		else Rgt=Mid;
	}
	for(int i=l;i<=Lft;i++){//就不要一个一个去pow了
		if(n%i==0)ans=min(ans,i+dfs(i,n/i,k-1));
	}return mp[l][n][k]=ans;
}
int main(){
	vector<int>v;
	read(n);read(k);
	int x=n;
	for(int i=2;i*i<=n;i++)
		while(x%i==0)x/=i,s+=i,v.push_back(i);
	if(x)s+=x,v.push_back(x);
	if(k>=v.size())cout<<s+k-v.size();//就是上面的式子
	else cout<<dfs(2ll,n,k);//2个优化一起来
	return 0;
}

最慢的点跑了0.015s。

我觉得这应该就是最优解了吧。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zhaohaikun/p/12816976.html