vijos - P1302连续自然数和 (公式推导 + python)
2024-08-30 22:40:58
P1302连续自然数和
标签:[显示标签]
描写叙述
对一个给定的自然数M,求出所有的连续的自然数段(连续个数大于1)。这些连续的自然数段中的所有数之和为M。
样例:1998+1999+2000+2001+2002 = 10000,所以从1998到2002的一个自然数段为M=10000的一个解。
格式
输入格式
包括一个整数的单独一行给出M的值(10 <= M <= 2,000,000)
输出格式
每行两个自然数,给出一个满足条件的连续自然数段中的第一个数和最后一个数,两数之间用一个空格隔开,全部输出行的第一个按从小到大的升序排列。对于给定的输入数据,保证至少有一个解。
例子1
例子输入1[复制]
10000
例子输出1[复制]
18 142
297 328
388 412
1998 2002这道题目假设用C++能够直接枚举,非常快就能够过,并且时间,可是这样对我们学习数论知识没有一点帮助。由于数论不仅仅是简单的枚举很多其它的是公式的推导,所以我对于数论题目尽可能的使用耗时长一点的语言。来让我将代码变得更加简短,高速,比方这道题目。用一种方法python超时,可是c++46ms就能够过了,可是假设我用python将这道题目过了,用c++直接就是0ms。我使用了一个公式推导式针对開始的前后两个数之差进行枚举计算m = math.sqrt(float(2 * n) + pow(a * 0.5,2.0)) - a * 0.5if m == int(m):
print i + 1,i + int(m)这个会超时,原因是,无论这个数符不符合条件,你都要进行这个式子的运算会导致这种结果,最后一个数据会超时:如此进行代码优化:对于等差数列公式得:(2a + m)(m + 1) = 2n -> 2a(m + 1) = 2n - m(m + 1) - > 2a = 2n / (k + 1) - m又由于a为整数所以。2n % (k + 1)不为零的直接排除,接着是(2n / (k + 1) - m) % 2不为零的能够排除这样非常多情况仅仅要推断一下就能够了,根本不须要进行什么计算。复杂度自然会降低非常多接着就是答案输出了这里提供pythonAC代码:#!/usr/bin/env python3
# -*- coding: utf-8 -*- import math
n = int(raw_input())
cnt = int(math.sqrt(2 * n))
i = cnt
while cnt > 0:
if not ((2 * n) % (cnt + 1)):
m = 2 * n / (cnt + 1)
m -= cnt
m >>= 1
if (2 * m + cnt) * (cnt + 1) / 2 == n and m >= 0:
print m,m + cnt
cnt -= 1
限制
最新文章
- Ninject之旅之八:Ninject插件模型(附程序下载)
- book
- Spring 一二事(3) - 别名
- Appnium移动自动化框架初探
- JAVA的可变类与不可变类
- Python字典--笔记
- oracle表空间扩容
- Viruses!!!!!
- BZOJ_1485_[HNOI2009]有趣的数列_卡特兰数
- RHEL/Centos7 安装图形化桌面(转)
- 清除eclipse项目中没用的图片、js、css代码
- Lintcode93-Balanced Binary Tree-Easy
- [leetcode]6. ZigZag Conversion字符串Z形排列
- IDEA搭建SSM实现登录、注册,数据增删改查功能
- Linux 上SSH 服务的配置和管理
- 【整理】fiddler不能监听 localhost和 127.0.0.1的问题
- 既生 Redis 何生 LevelDB ?
- Selenium2+python自动化47-判断弹出框存在(alert_is_present)
- win10 U盘安装ubuntu16.04双系统
- 【转】httpservlet 文章
热门文章
- magento 购物车 首页 显示
- Assembly之instruction之JC
- java对于07excel的读、改、写、并触发计算
- Extensions can add new functionality to a type, but they cannot override existing functionality.
- Description	Resource	Path	Location	Type Missing artifact com.********:framework:jar:1.0.2	pom.xml	/项目名	line ****	Maven Dependency Problem
- EasyUI_datagrid
- 链表相关的leetcode重要题目
- 荷兰国旗问题、快排以及BFPRT算法
- 数列分块入门1-9 By hzwer
- Go:内置函数