当前位置：首页 > 编程日记 > 正文

1096 Consecutive Factors

编程日记 2024-09-07 18:50:00

1. 对于题目描述中 list the smallest sequence of the consecutive factors 正确理解是：如果有多组连续因子，输出开头因子最小的那个序列(一开始理解成输出数目最小的那个序列)

2. 想象一下这种情况，2*3*4*5 = 120，4*5*6 = 120，如果只遍历不去改变n，那么会最大连续因子是5的错误结果。但是如果一边遍历，一遍除以n，想象这种情况 2*3*5*7，2*3如果得到6的话，最大的连续个数就是3(5*6*7)，但由于一开始把2就除掉，因此会得到2的错误结果。所以也不能一遍遍历一遍除。只能采用对于每一个因子，往下走看看，看看最远能走到哪一步，然后不断更新这个最远的数字。

3. 对于中间那个长度len = j-i要不要加减一，与其硬想，不如debug来确定。

4. 这题对于数学功底的要求是，明白连续的质因子要出现也只会出现在2到根号n以内，如果在2到根号n以内一个质因子都没有，那就输出那个数自身。（其实可能在(sqrt(n),n)之间有一个质因数，只不过数据不强，没测出来）

AC代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
#include<stdlib.h>
#include<time.h>using namespace std;
typedef long long LL;const int maxn = 10007;
const int MOD = 1000000007;
const int INF = 1000000000;//INF:下确界  
const LL SUP = (1LL<<63)-1;//SUP:上确界 
const double eps = 1e-5;int main(){LL n;//虽然n是在int范围内，但是后面会涉及乘积 scanf("%lld",&n);LL sqr = (int)sqrt(1.0*n);//这个连续乘积不会出现在根号n之后 int max_conse = 0;LL max_begin = 0;for(int i=2;i<=sqr;i++){if(n%i==0){int temp = 1;int len;for(int j=i;n%temp==0;j++){//2*3*4temp *= j;len = j-i;}		if(len>max_conse){max_conse = len;max_begin = i;}}}if(max_conse==0){printf("1\n");printf("%lld\n",n);return 0;} printf("%d\n",max_conse);for(int i=max_begin;i<max_begin+max_conse;i++){printf("%d",i);if(i!=max_begin+max_conse-1)printf("*");}return 0;
}

AC代码2

#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<string>using namespace std;const int maxn = 2000;typedef long long ll;int n;int getConFac(int n,int f){int num = 0;for(int i=f;i<=n;i++){if(n%i==0){n /= i;num ++;}else break;}return num;
} int main(){cin>>n;int maxNum = 0;int maxBF;//begin factorfor(int i=2;i<=sqrt(n);i++){if(n%i==0){int tempNum = getConFac(n,i);if(tempNum>maxNum){maxNum = tempNum;maxBF = i;}}}if(maxNum==0){printf("%d\n%d",1,n);return 0;}printf("%d\n",maxNum);for(int i=maxBF;i<maxBF+maxNum;i++){printf("%d",i);if(i!=maxBF+maxNum-1)printf("*");}return 0;
}

https://www.dkcj.cn/info/17718.html

1096 Consecutive Factors

相关文章：

百度DisConf分布式配置框架源码试读（一）HttpClient 长连接

开篇第一题：经典中的经典！

(C++)高精度整数的存储、读入、比较和四则运算

TP-link 设置MAC地址过滤

flask的客户端服务端

1023 Have Fun with Numbers

Oracle中Hint深入理解(原创)

css sprites之圆角

爬虫原理与数据抓取----- urllib2：URLError与HTTPError

1024 Palindromic Number

HibernateTemplate 查询

EMQ学习笔记---Clean Session和Retained Message

JPA相关--Annotation

(C++)变长数组vector的常见用法

【kuangbin专题】计算几何_半平面交

设计模式之状态模块加观察者模式

objectdatasource中delete的尴尬。

1039 Course List for Student

《编程匠艺》读书笔记

【转】C语言的memset函数

一个6年iOS程序员的工作感悟，送给还在迷茫的你

1063 Set Similarity

Volume是如何工作的

使用 TFDConnection 的 pooled 连接池

Java与UML交互图

1054 The Dominant Color

通过sqlserver日志恢复误删除的数据

关于在phpStudy环境下，windows cmd中 php不是内部命令问题

如何用javascript控制上传文件的大小

1071 Speech Patterns 需再做