美文网首页
A1096 Consecutive Factors (20分)

A1096 Consecutive Factors (20分)

作者: km15 | 来源:发表于2020-02-13 16:27 被阅读0次

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

2、解题:
1、N不会被除自己以外的大于根号N的整数整除,
2、因此只需要从2~根号N遍历连续整数的第一个,求此时N能被最多多少个连续整数的乘积整除
3、在此过程中,如果有发现长度比当前最长长度anslen更长的情况,就更新ansLen和对应的第一个整数anl

learn && worng:
1、需要用longlong ,而不是Int,防止相乘溢出
2、注意是这一点,从第一个因子开始,不断连续乘积,都可以被整除,因为都是因子,所以因子乘因子仍是因子的一部分
包括:
找到第一点
计算长度并更新

*/

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long LL;
 
int main(int argc, char** argv) {
    LL n;
    scanf("%lld",&n);
    //sqrt为根号N,anslen为最长年连续整数,ansi为对应第一个整数
    LL sqr = (LL)sqrt(1.0 * n),ansi = 0,anslen = 0;
    for(LL i = 2;i<=sqr;i++){   //遍历连续的第一个整数
         LL temp = 1,j = i; //temp为当前连续整数的乘积
         while(1){  //让j从i开始不断+1,看最长能到多少
            temp *= j;  //获得当前连续整数的乘积  
            if( n % temp != 0) break;   //如果不能整除n,那么结束计算
            if(j - i + 1 > anslen){ //发现更长长度 
                ansi = i;   //更新第一个整数
                anslen = j - i + 1;//更新最长长度 
            }
            j++; //j加1,下一个整数     
        }
    
    }
    
    if(anslen == 0){    //最大长度为0,说明根号N范围内没有解
        printf("1\n%lld",n);    //输出n本身  
    }else{
        printf("%lld\n",anslen);    //输出最大长度
        for(LL i = 0;i < anslen;i++){
            printf("%lld",ansi+i);
            if(i< anslen - 1){
                printf("*");    //!!!输出间隔的乘号 
            }
        } 
    }
    return 0;
}


相关文章

网友评论

      本文标题:A1096 Consecutive Factors (20分)

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