网站书店架构书怎么做,投资理财网站开发制作,上海设计网站,大丰网站建设题目链接 实现方法 本题分为两步#xff1a;
质因数分解#xff1b;数字重排序#xff08;相同数字不连续#xff09;
质因数分解使用线性筛法#xff0c;并在求质因数的过程中不断减小原数字。 数字重排序与重排字符串方法相同。
使用有序集合multiset存放各质因数及…题目链接 实现方法 本题分为两步
质因数分解数字重排序相同数字不连续
质因数分解使用线性筛法并在求质因数的过程中不断减小原数字。 数字重排序与重排字符串方法相同。
使用有序集合multiset存放各质因数及其出现次数判断是否存在可行解最多的次数ma是否超过总次数sum的一半奇数为masum/21;先轮流输出次数最多和次数第二多的数字直到最多的次数与第二多的次数相等循环依次输出剩余的所有数字需要判断第3步输出的最后一个数字和第4步输出的第一个数字是否相同相同需要交换顺序
代码
#include bits/stdc.h
using namespace std;
//输入的正整数范围超过了int的最大值需要用long long
#define int long long
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;//使用map记录各质因数与其出现的次数mapint,intm;cinn;//1不是素数需要特判if(n1)return cout-1,0;for(int i2;i*in;i){while(n%i0){m[i];n/i;}}if(n1)m[n];//使用multiset对质因数和出现次数重排序并记录出现最多的次数multisetpairint,ints;int sum0,ma0;for(auto j:m){sumj.second;mamax(ma,j.second);s.insert({j.second,j.first});}//判断是否存在可行解if(2*ma-1sum)return cout-1,0;coutsumendl;if(s.size()1){cout(*s.begin()).secondendl;return 0;}int x;//while(sum0){auto temp*s.rbegin();s.erase(temp);auto temp2*s.rbegin();s.erase(temp2);if(temp.first!temp2.first){couttemp.second ;temp.first--;if(temp.first){couttemp2.second ;xtemp2.second;temp2.first--;}else break;s.insert(temp);s.insert(temp2);}else{s.insert(temp);s.insert(temp2);break;}sum--;}vectorpairint,intv;for(auto i:s){v.push_back(i);}while(1){int jud0;for(int iv.size()-1;i0;i--){if(v[i].first){coutv[i].second ;v[i].first--;jud1;}}if(!jud)break;}return 0;
}
