美文网首页
L1-006. 连续因子(思想较为复杂)

L1-006. 连续因子(思想较为复杂)

作者: mztkenan | 来源:发表于2017-03-14 20:25 被阅读1605次

一个正整数N的因子中可能存在若干连续的数字。例如630可以分解为356*7,其中5、6、7就是3个连续的数字。给定任一正整数N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。

输入格式:

输入在一行中给出一个正整数N(1<N<231
)。

输出格式:

首先在第1行输出最长连续因子的个数;然后在第2行中按“因子1因子2……*因子k”的格式输出最小的连续因子序列,其中因子按递增顺序输出,1不算在内。

输入样例:

630

输出样例:

3
567

分析:N的范围是 1<N<2^31,经过计算,12!=479001600 < N < 13!=6227020800,也就是说,最长的连续因子的个数不会超过12个。那最初考虑枚举N的所有因子分解,从中选择最长连续因子,可是实现起来有点麻烦,思路很乱。
其实并不需要得到N的因子分解,只需要取其中的连续因子的部分即可。实现思路为,从最大长度12开始枚举,因子的范围是[2, sqrt(n)+1)],只需要判断一段连续因子的乘积是否为N的因子即可。长度从大到小,因子从小到大枚举,因此最先得到的序列一定是最长的。且最小的。

#include <iostream>
#include<math.h>
using namespace std;
//一个数,质数
int main()
{
    bool isFound;
    long long int n,ans;
    int len,END,start=2;//max表示最大的因数,重要,要关注特殊情况,144,6,
    while(cin>>n){
        isFound=false;
        END=sqrt(n)+1;
        for (int i=12;i>=1;i--){  //i表示最最长序列个数,不会超过12,非常重要!注意=1的边界情况,可能所有因子都是不连续的

            for (start=2;start<=END;start++){
                    ans=1;
                for (int j=start;j-start<=i-1;j++){ //j表示最左边的节点
                    ans*=j;
                }
                //cout<<"ans"<<ans<<endl;
                if(n%ans==0){
                    isFound=true;
                    len=i;
                    break;
                }

            }
            if(isFound==true) break;
        }
        if(isFound==true){
            cout<<len<<endl;
            for (int i=0;i<len-1;i++){
            cout<<start+i<<"*";
        }
            cout<<start+len-1;
        }
        else{
            cout<<"1\n";
            cout<<n;
        }
    }


    return 0;
}

第二种方法:直接进行

#include <iostream>
#include<math.h>

using namespace std;

int main()
{
    int num,count,temp,start,product;
    while(cin>>num)
    {
        count=0,temp=0,start=0;
        for (int i=2; i<sqrt(num)+2; i++) //限制范围,为何加5,特例8,特例6,只有2这个因数,不往后加一个,无法使得count++
        {
            product=1;
            for (int j=0; true; j++)
            {
                product*=(i+j);
                if(num%product==0)
                {
                    temp=j+1;//j是i之后的数字,所以要加1
                }
                else
                {
                    break;
                }
            }

            if(count<temp)
            {
                count=temp;//cout<<"B"<<count<<endl;
                start=i;
            }
            //cout<<" C"<<count<<endl;
            temp=0;

        }
        if(count!=0)
        {
            cout<<count<<endl;
            for (int i=start; i<start+count; i++)
            {
                if(i==start)
                    cout<<i;
                else
                    cout<<"*"<<i;
            }
        }

        else
        {
            cout<<"1\n";
            cout<<num;
        }


    }

    return 0;
}


第一种纠结之处

1.不仅要关注是质数的情况,更要关注所有因数都不连续,此时要输出的最小序列不是他本身,如357=105,所以要考虑i=1的情况
2.数字相乘可能溢出,使用long long int
3.先解决范围,缩小到12使得复杂度大大减小,,这里的12是12个因数,这种缩小思路很难得
3.三重循环之间的变量不要绕晕了

第二种纠结之处

1.刚开始从2进行遍历,若连续几个都为因子则数量增加,错误在于是因子,但是乘起来并不一定是因子。这里可以看到通过了四个用例,看来内部用例较小
2.特殊情况,质数,则count=0,输出要特殊列出

相关文章

  • L1-006. 连续因子(思想较为复杂)

    一个正整数N的因子中可能存在若干连续的数字。例如630可以分解为356*7,其中5、6、7就是3个连续的数字。给定...

  • Kubernetes Dashboard token失效时间设置

    升级了新版本的Dashboard(这里使用的v1.8.3),使用了较为复杂的双因子登录,正确输入用户名和密码之后还...

  • 非连续性文本阅读

    课标:阅读由多种材料组合,较为复杂的非连续性文本,能领会文本的意思,得出有意义的结论。非连续性文本定义: 非连续性...

  • 因子预测能力初探 ——多因子模型系列报告之一

    投资要点:  在多因子选股模型中,IC 通常被用于衡量因子对收益率的预测能 力,本文选取较为广泛应用的因子,利用...

  • 复杂思想

    甲:当你觉得一切很奇怪的时候,其实并不奇怪,因为你未曾实际的经历过;当你觉得一切不奇怪的时候,其实有点奇怪,因为别...

  • 复杂思想

    最近一段时间里面,总是会有“时间不够用”的感觉,在固定的时间里面,好像没什么可以扩展的东西,但是转念一想,可能还是...

  • 因子变换

    Alhpa 模型的实质是通过找到因子或因子组合与未来收益率之间的关系,从而训 练出较为稳定的收益预测函数,选取优质...

  • A1096 Consecutive Factors (20分)

    /*题意:1、找出连续的因子,最多的个数,然后因子大小要最小输入:输入一个数字,最大是int的最大输出:输出连续依...

  • R 学习笔记(5) -- 因子和表

    因子 因子 (factor) 是 R 语言中许多强大运算的基础,包括许多针对表格数据的运算。因子的设计思想来源于统...

  • 读考纲 看变化 明方向

    2011版《语文课程标准》指出,初中学生要能“阅读由多种材料组合、较为复杂的非连续性文本,能领会文本的意思,...

网友评论

      本文标题:L1-006. 连续因子(思想较为复杂)

      本文链接:https://www.haomeiwen.com/subject/hflngttx.html