P7947

Fish_and_Chips_ · 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;
}