PAT A1096 Consecutive Factors （20 分）—

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:

Sample Output:

3

5*6*7

 #include <stdio.h>

 #include <algorithm>

 #include <set>

 #include <string.h>

 #include <vector>

 #include <queue>

 using namespace std;

 typedef long long ll;

 const int maxn = ;

 ll n;

 int main(){

     scanf("%lld",&n);

     ll res=,res_j=,res_i=;

     for(ll i=;i*i<=n;i++){

         ll sum=,j=i;

         while(){

             sum*=j;

             if(n%sum!=)break;

             j++;

         }

         j--;

         if(j-i+>res){

             res=j-i+;

             res_j=j;

             res_i=i;

         }

     }

     if(res==) {

       printf("1\n%lld",n);

       return ;}

     printf("%lld\n",res);

     for(int i=res_i;i<res_j;i++){

         printf("%lld*",i);

     }

     printf("%lld",res_j);

 }

注意点：一开始找成了所有因子都连续，结果一直是0，后来发现只要能整除就好了。其实和找质数也差不多

第二点是要用long long 不能用int，虽然题目输入是int范围，但是你的乘积结果会超int，导致死循环。

第三点是遍历上限到sqrt(n)就好了，否则会超时，因为sqrt(n) * (sqrt(n)+1) 肯定大于n了。

第四点是遇到质数要输出自己，不是只判断2和3就好了，只要看res是不是还是0。

巴特西

PAT A1096 Consecutive Factors （20 分）——数字遍历

Input Specification:

Output Specification:

Sample Input:

Sample Output:

最新文章

热门文章