[C语言]连续因子—–穷举

文章目录[隐藏]

前言
题目
正式处理
贴代码
总结

前言

额，这个题好像有点问题（同学指出的，我也同意这个问题），详见题目中的修改部分

题目

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

输入格式：

输入在一行中给出一个正整数 $N$ （ $1 < N < 2^{³¹}$ ）。

输出格式：

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

输入样例：
630
输出样例：
3
5*6*7

为什么有问题 #(疑问)

对于630可以分解成2*3*3*5*7或3*5*6*7

很明显根据输出判断，结果要的是最长的具有连续性的因子（前者最长连续为2*3，相较于后者的最长连续为5*6*7显然短了）

因此，判断题目描述不正确。

思路

根据上面的分析，可以知道输出的这一串连续因子的乘积是输入值的因子，

那么可以制造一个比较长的连续因子的乘积（越长意味着这个积的因子起始值较小），比如2*3*4*5*6*7*8*9 ，

并且这个积开始要大于甚至等于输入值。

为什么要靠近？

因为，存在一些这样的数：2*3*4*5*6 = 720，懂了吧 #(滑稽)

然后用输入值对其进行取余操作，如果取余结果是0就输出，否则就改变积的组成

如何改变积的组成？

像这样：

从最长长度开始，每次都把某一固定长度的所有可能情况都过一遍。

如何判断最长长度？

题目给出了输入值的范围： $N$ （ $1 < N < 2^{³¹}$ ）

而我们判断最长长度的因子的乘积大小为n!（假设最长长度为n-1）

因为，2³¹ = 2 147 483 648，13! = 6 227 020 800，12! = 479 001 600

12! < 2³¹ <13! ，由此可以设定长度为12，即最长长度的因子的乘积大小为13!

正式处理

1.由于是在固定因子长度的情况下穷举所有连续可能性，因此第一层循环为因子长度（即数量）

2.确定长度后，要执行的操作是从2开始依次往后移动起始值，于是，第二层循环为因子起始值的改变（为什么用循环？这不是废话吗 #(受虐滑稽) ）

3.确定长度与起始值后，根据这两个来计算“因子”的乘积（累乘，不过存储的容器最好大点 #(流汗滑稽) ），

4.用输入值对得到的积进行取余，为0就说明就是它了，别找了，输出一下就跑了 #(cos滑稽)

不是0就让起始值后移，不能后移就减小长度。。。。。

注意：起始值的确定

如果a*b = c（a<b），那么当a增加到b时，b也相应的减少到a。

因此，当a=b=√c 时a就算是到达最大值了。

对于本题若起始值是a，同时我们默认b>a总是成立（因为后面的值至少比a大1），

所以一旦a超过√c（这里的c是输入值），连续因子的积必然大于输入值；

所以，后面的操作都是无意义的

贴代码

还是那样，代码并非最优，仅供参考。你可以将累乘写成函数，那样程序将具有模块化风格。

/**
 * 一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7，其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。
 * 输入在一行中给出一个正整数 N（1<N<2的31次方 ）。
*/

#include <stdio.h>
#include <math.h>

int main(void)
{
    int N;
    int m;
    int len;
    int i,j,t;
    int max;
    long long int sum;
    scanf("%d", &N);
    max = sqrt(N);

    //定长度
    for (len = 11; len >= 1; len--)
    {
        //定起始值
        for (j = 2; j <= max; j++)
        {
            //初始化
            sum = 1;
            m = len;
            t = j;

            //累乘
            while (m--)
            {
                sum *= t++;
                if (sum > N)
                {
                    break;
                }
                
            }

            //取余
            if (N % sum == 0)
            {
                printf("%d\n%d", len, j);
                for (i = j+1; i < t; i++)
                {
                    printf("*%d", i);
                }
                return 0;
            }
            
        }
    }

    printf("1\n%d\n", N);
    return 0;
}