自动搬运

查看原文

来自洛谷，原作者为

	InterN_NOT_FOUND 请记得我 || 代词使用她 || o((>ω< ))o

搬运于2025-08-24 22:34:32，当前版本为作者最后更新于2021-11-18 17:57:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

忘了打月赛了掉了很多比赛咕值所以写篇题解防止掉绿。

这个题意就是让我们把 $n$ 拆成若干数相乘的形式，使这些数相加等于 $k$ 。

所以很快就能想到一个方法：质因数分解。

把 $n$ 质因数分解后再拿分解后的因数加起来凑成 $k$ 就好了。

上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline bool isnum(char ch){return ch>='0'&&ch<='9';}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isnum(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isnum(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void out(int x,char ch){
    if(x<0){putchar('-');x=-x;}
    if(x>9)out(x/10,'/');
    putchar(x%10+'0');
    if(ch=='l')putchar('\n');
    if(ch=='s')putchar(' ');
}

//习惯用缺省源

int n=read(),k=read(),a[114514],len,sum;
signed main()
{
	for(int i=2;i<=n;i++){//质因数分解
		while(n%i==0){
			a[++len]=i;
			n/=i;
			sum+=i;
		}
	}
	if(sum==k){//如果分解后所有因数的和等于k，那直接输出即可
		out(len,'l');
		for(int i=1;i<=len;i++)out(a[i],'s');
	}
	if(sum<k){//如果分解后所有数的和小于k，那在后面补1即可（不改变积）
		out(len+k-sum,'l');
		for(int i=1;i<=len;i++)out(a[i],'s');
		for(int i=1;i<=k-sum;i++)out(1,'s');
	}
	if(sum>k){out(-1,'l');return 0;}//如果分解后所有数的和大于k，那么就不存在这样的数列。因为除1以外的正整数相乘积都不可能小于它们的和。
	return 0;
}