记录一道昨天卡住的题问题链接
给你一个整数\(n\)，你可以进行最多\(1000\)次操作，使得\(n\)减去它的一个因数，要求每种减数至多出现两次
我们考虑先把\(n\)进行质因数分解，得到质因数序列\(P\) \(\{ p_1 , p_2, ... ,p_m\}\)
我们从中取出一个最大的质因数\(x\)，然后让\(n\)减去\(\frac{n}{x}\)，也就是\(\frac {\prod p_i}{x}\)，接下来再把\(x-1\)分解质因数并放回序列
试想，只有质因数除去最大值外，其他数字累乘相等时才会出现减数重复现象，而\(x-1\)不为\(1\)时\(x-1\)一定可以分解，可以发现除去最大值外所有数字相乘的状态是不可逆的，除非\(P\)仅包含一个质数
而\(P\)只有在初状态和末状态可能是单个质数
得证
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll>ans;
priority_queue<ll>q;
void solve(){
ll n,now;
ans.clear();
scanf("%lld",&n);
now=n;
for(int i=2;i*i<=n;i++){
while(n%i==0){
n/=i;
q.push(i);
}
}
if(n>1)q.push(n);
ans.push_back(now);
while(!q.empty()){
int t=q.top();
q.pop();
now=now/t*(t-1);
t--;
ans.push_back(now);
for(int i=2;i*i<=t;i++){
while(t%i==0){
q.push(i);
t/=i;
}
}
if(t>1)q.push(t);
}
printf("%d\n",ans.size());
for(int j=0;j<ans.size();j++)
printf("%lld ",ans[j]);
puts("");
}
int main(){
int t=1;
scanf("%d",&t);
while(t--)solve();
return 0;
}