PAT_A1096#Consecutive Factors
2024-08-29 12:10:41
Source:
Description:
Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3×5×6×7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.
Input Specification:
Each input file contains one test case, which gives the integer N (1<N<).
Output Specification:
For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format
factor[1]*factor[2]*...*factor[k]
, where the factors are listed in increasing order, and 1 is NOT included.
Sample Input:
630
Sample Output:
3
5*6*7
Keys:
Attention:
- 注意质数的情况
- 若n存在因子factor0,使得factor0*factor0>n,则factor0唯一;即其余factor,全部有factor*factor<=n
Code:
/*
Data: 2019-07-08 19:35:10
Problem: PAT_A1096#Consecutive Factors
AC: 31:02 题目大意:
正整数N可以分解为多组因数乘积的形式,选择含有最长连续因数的一组,打印该连续因数
因数中不含1,打印序列递增且较小的
*/
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL; int main()
{
LL n;
scanf("%lld", &n);
vector<LL> ans,temp;
for(LL i=; i<=(LL)sqrt(1.0*n); i++)
{
LL sum=;
temp.clear();
for(LL j=i; j<=n; j++)
{
sum *= j;
if(n%sum != )
break;
temp.push_back(j);
}
if(temp.size() > ans.size())
ans = temp;
}
if(ans.size()==)
printf("1\n%lld", n);
else
printf("%d\n", ans.size());
for(int i=; i<ans.size(); i++)
printf("%d%c", ans[i], i==ans.size()-?'\n':'*'); return ;
}
最新文章
- hadoop 2.7.2 和 spark1.6 多节点安装
- JavaWeb---总结(四)Tomcat服务器学习和使用(二)
- 导入 sun.net.TelnetInputStream; 报错
- 重力加速度陀螺仪传感器MPU-6050(一)
- Java单例模式深入详解
- 转:Eclipse Kepler已支持Java 8
- 蓝桥杯算法训练<;一>;
- -Swift.h not find
- Example013操作样式
- 自己动手修改Robotium代码(下)
- not in 前面/后面存在null值时的处理
- Win10系列:C#应用控件基础11
- linux下安装redis组件报错-gcc报错
- linux-Centos 7下tftp-server服务的安装与配置
- Spring的两种动态代理:Jdk和Cglib 的区别和实现
- jdb--gdb---java 远程调试(java application与web application)
- ubuntu14.04 login loop issue
- CocoStuff—基于Deeplab训练数据的标定工具【四、用该工具标定个人数据】
- windows环境下的heap spray+stack pivot gadget 实现绕过dep
- MySql 数据库导入";Unknown command &#39;\n&#39;.";错误解决办法