当前位置: 代码迷 >> 综合 >> 【一败涂地】L1-006 连续因子 (20分) 题解
  详细解决方案

【一败涂地】L1-006 连续因子 (20分) 题解

热度:90   发布时间:2023-11-17 23:23:05.0

【一败涂地】L1-006 连续因子 (20分) 题解

很晃很暴力

题目链接:L1-006 连续因子 (20分)

题目

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

输入

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

输出

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

样例输入

630

样例输出

3
5*6*7

题意

有一点坑

  • 首先就是你求出来的这几个 连续因子 它们的乘积不能大于这个N
  • 其次就是写程序的时候要注意: 不要 找所有因子中连续的部分,而要 连续的找可以用的因子 我就是思路错了硬生生卡了三天= =最后被迫搜题解了

解题思路

明确了思路以后这道题其实很好暴力了。

从 2 开始遍历到 根号n 。(根号n 是个神奇的数字)然后从每一个数字开始依次往后加一用n取余,如果最后把n除完了或者取余不为0了就停止记下长度以及开头结尾。加个判断取最大值就好了~

对了最后还要加个特判,如果是素数的话直接输出自己就好辣。

代码

#include <iostream>//记得如果用i*i<n的方法来判断根号的话要用long long哟~
typedef long long ll;using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);ll t, x; cin >> t;ll a = 2, b = 2, l = 0;for (ll i = 2; i*i < t; i++) {ll n = t, j = i;while (n % j == 0) n /= j, j += 1;if (l < j - i) l = j - i, a = i, b = j;}if (l) {cout << l << endl << a;for (int i = a + 1; i < b; i++) {cout << '*' << i;} cout << endl;} else cout << '1' << endl << t << endl;return 0;
}