题目链接:点击打开链接
题目大意:求尽可能多连续相乘的因子个数,并输出连续因子,若有相等因子个数的情况,取最小的因子开始。
解题思路:因为 2^31 值在 12!~13! 之间,所以撑死循环 13 次就可以结束,复杂度就可以直接上暴力,而大循环控制从 2 开始,到 sqrt(n) 结束;内循环控制当中连续的情况。注意:质数的情况(特殊)。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; vector<int> tv,v; int main() { int n; while(~scanf("%d",&n)) { v.clear(); int rs=0, ma=sqrt(n); for(int i=2;i<=ma;i++) // 非质数 { int j=i,cnt=0,tn=n,carr=0; tv.clear(); while(tn!=0&&carr<13) { if(tn%j==0) tv.push_back(j), tn/=j, cnt++; else { if(cnt>rs) rs=cnt, v=tv; cnt=0; tv.clear(); } j++; carr++; } if(cnt>rs) rs=cnt, v=tv; // 最后一次也是答案之中,特判 } if(v.size()==0) printf("1\n%d\n",n); // 质数 else { printf("%d\n",v.size()); for(int i=0;i<v.size()-1;i++) printf("%d*",v[i]); printf("%d\n",v[v.size()-1]); } } return 0; }