Consecutive Factors(求最大连续因数序列)

2024-03-17 00:30

本文主要是介绍Consecutive Factors(求最大连续因数序列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述 Among all the factors of a positive integer N, there may exist
several consecutive numbers. For example, 630 can be factored as
356*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.

输入描述: Each input file contains one test case, which gives the integer
N (131).

输出描述: 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.

输入例子: 630

输出例子: 3 567

PAT上的一个题,给定一个数N,要求这个数的最长连续因数,如果答案不唯一则取最小的因数序列(比如给了30,则有2*3和5*6,结果取5*6)并且1不计算在结果序列里面。

设结果序列中最小值为i,当i=sqrt(N)的时候,这个序列的最大长度为1(sqrt(N)*(sqrt*(N)+1)>N),可知i不会大于sqrt(N)。因此我们只需要令i=[2,sqrt(N)] ,依次寻找由i打头的最大序列并且记录即可。并且由于题目中要求的是不同答案中取i最小的那个序列,所以每次要当新的序列长度>max_len的时候才更新记录。

要注意的一点是,如果由2到sqrt(N)都找不到一个长度至少为1的序列,那么就说明这个数是个素数,那么这个序列应该为N本身,长度为1(1不包括在序列里)。

#include <iostream>
#include<math.h>
using namespace std;int main() {int N;cin >> N;int j = sqrt(N) + 1, max_len = 0, idx = -1;for (int i = 2; i < j; i++) {if (N % i != 0) continue;int t_len = 0, t_N = N,t_idx=i;while (t_N && t_N % t_idx == 0) {t_N /= t_idx;t_idx++,t_len++;}//这里>不能改成>=if ( t_len > max_len) {max_len = t_len;idx = t_idx-t_len;}}//找不到则序列为N本身if (idx == -1) {idx = N;max_len = 1;}cout << max_len << endl;for (int i = idx; i < idx + max_len; i++) {cout << i << ((i == idx + max_len - 1) ? "" : "*");}}

测试结果:
在这里插入图片描述
值得一提的是,这个算法的复杂度跟所给定整数的长度有关系,题目给的是int,占32位,最大值为2^31-1=2147483647,而12!=479 001 600,13!=6 227020800,既12!<intMax<13!,因此max_len的最大值不会超过11。并且由于是阶乘增长,随着i的变大max_len的最大值是会变小的,所以实际上平均下来max_len的最大值应该是比11小的。因此时间开销应该<11*sqrt(N)∈O(sqrt(N))

这篇关于Consecutive Factors(求最大连续因数序列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/qq_34025034/article/details/106497973
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/817241

相关文章

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

PostgreSQL 序列(Sequence) 与 Oracle 序列对比差异分析

《PostgreSQL序列(Sequence)与Oracle序列对比差异分析》PostgreSQL和Oracle都提供了序列(Sequence)功能,但在实现细节和使用方式上存在一些重要差异,... 目录PostgreSQL 序列(Sequence) 与 oracle 序列对比一 基本语法对比1.1 创建序

详解C++中类的大小决定因数

《详解C++中类的大小决定因数》类的大小受多个因素影响,主要包括成员变量、对齐方式、继承关系、虚函数表等,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 非静态数据成员示例:2. 数据对齐(Padding)示例:3. 虚函数(vtable 指针)示例:4. 继承普通继承虚继承5.

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o