1096 Consecutive Factors (20分)[因数]
程序员文章站
2022-06-07 11:44:52
...
By Jalan
知识工具需求
题干
给一个数求最长连续因数(注意不是质因数)
例子
例1
输入
630
输出
3
5*6*7
例2
输入
6
输出
2
2*3
例3
输入
7
输出
1
7
题解
第一次
思路
注意这个题不是简单的因数分解,而是求有没有连续的因数,因此策略应该是一个一个除,再可以整除的时候循环检测接下来几位能不能整除,统计本次可以整除的数量和末位.
还要注意连续因子序列可以只有1个,而外圈,即是否能整除检验终止在(内圈,向前几位能整除不用,因为会很快die掉),因此在sqrt检测光但是还是没有整除的时候,应该把连续数量设置成1,连续值设置成n.
这个题看着规模很大但是实际上规模是很小的,对于除法来说,就已经比INT32_MAX
大了,所以实际上再暴力都会很快.
编写用时
30分钟
代码
CPP
#include <cmath>
#include <stdio.h>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
int temp = 2;
int sq = sqrt(n);
int maxValue = 0;
int maxCounter = 0;
while (temp <= sq) //外圈,检测是否当前位能整除
{
int div = n / temp;
if (div * temp == n) //在出现能整除时得检验可以向前再整除几位.
{
int temp2 = temp + 1;
int temp2Counter = 1;
while (temp2 <= n) //内圈,检测能向前再整除几位
{
int div2 = div / temp2;
if (div2 * temp2 == div)
{
div = div2;
temp2Counter++;
temp2++;
}
else
{
break;
}
}
//temp=temp2,我第一次调试的时候把这句注释掉了,一个是性能足够没必要,一个是确实加速会导致错误的.
if (temp2Counter > maxCounter)
{
maxCounter = temp2Counter;
maxValue = temp2 - 1;
}
}
temp++;
}
if (temp > sq && maxCounter == 0) //处理质数
{
maxCounter = 1;
maxValue = n;
}
//output
printf("%d\n", maxCounter);
for (int i = 0; i < maxCounter; i++)
{
printf("%d", maxValue - maxCounter + 1 + i);
if (i != maxCounter - 1)
{
printf("*");
}
}
return 0;
}
运行用时
结尾
看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀
@aaa@qq.com
也欢迎关注我的CSDN账号呀=]
**开心code每一天**