Skip to content

L1-006 连续因子

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

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

输入格式

输入在一行中给出一个正整数 N（1）。

输出格式

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

输入样例 

630

输出样例 

3
5*6*7

鸣谢用户 漏穿雪 补充数据！

Solution

#include <ctype.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long LL;

const double PI = 3.14159265358979323846264338327;
const double E = 2.718281828459;
const double eps = 1e-6;

const int MAXN = 0x3f3f3f3f;
const int MINN = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;

int a[maxn];

int main() {
    int n;
    cin >> n;
    int i, j;
    int vis = sqrt(n) + 1;
    memset(a, 0, sizeof(a));
    int temp;
    for (i = 2, j = 0; i <= vis; i++) {
        if (n % i == 0)
            a[j++] = i;
    }
    int len = j;
    int max = 0, ans;
    LL sum;
    for (i = 0; i < len; i++) {
        sum = a[i];
        vis = 1;
        for (j = 1;; j++) {
            sum *= (a[i] + j);
            if (n % sum != 0)
                break;
            else
                vis++;
        }
        if (vis > max) {
            max = vis;
            ans = a[i];
        }
    }
    if (len == 0) {
        cout << 1 << endl;
        cout << n << endl;
    } else {
        printf("%d\n", max);
        for (i = 0; i < max; i++) {
            if (i)
                printf("*");
            printf("%d", ans + i);
        }
        cout << endl;
    }
}
Last update: May 4, 2022
Back to top